#6095. 花神的嘲讽计划

题目背景

花神是神，一大癖好就是嘲讽大 J。这一天 DJ 在给众蒟蒻讲题，花神在一边无聊，就一起来听。花神常常会打断大 J 并嘲讽他，让他尴尬。

题目描述

大 J 的讲课方案是一个长度为 $n$ 的数列。
花神有 $m$ 个嘲讽方案，每个嘲讽方案是一个长度为 $k$ 的数列。
每次花神会在区间 $[x, y]$ 这段时间内进行嘲讽，条件是：

• 如果大 J 在讲课方案的 $[x, y]$ 这个区间中的任意连续 $k$ 个数的子段里，没有花神的某个嘲讽方案（长度为 $k$ 的数列），那么花神就会嘲讽大 J，让他尴尬。
• 否则（即区间中存在该嘲讽方案），大 J 不会尴尬。

简单说：每次询问给一个区间 $[x, y]$ 和一个长度 $k$ 的数列（嘲讽方案），问在 $[x, y]$ 中是否存在一个连续 $k$ 项的子数组，正好等于这个数列。

输入格式

第一行三个整数 $n$, $m$, $k$。
第二行 $n$ 个整数，表示大 J 的讲课方案序列。
接下来 $m$ 行，每行 $k+2$ 个整数：

• 前两个是 $x$ 和 $y$（$1 \le x \le y \le n$）；
• 后面 $k$ 个整数，表示花神的嘲讽方案。

输出格式

对于每个询问，如果会尴尬（即区间内不存在该嘲讽方案），输出 Yes，否则输出 No。

样例

输入

8 5 3
1 2 3 4 5 6 7 8
2 5 2 3 4
1 8 3 2 1
5 7 4 5 6
2 5 1 2 3
1 7 3 4 5

输出

No
Yes
Yes
Yes
No

解释

1. $[2,5]$ 中有子段 $[2,3,4]$，与 $(2,3,4)$ 相同，所以 No（不尴尬）。
2. $[1,8]$ 中没有子段 $(3,2,1)$，所以 Yes（尴尬）。
3. $[5,7]$ 中没有子段 $(4,5,6)$，所以 Yes。
4. $[2,5]$ 中没有子段 $(1,2,3)$，所以 Yes。
5. $[1,7]$ 中有子段 $(3,4,5)$，所以 No。

数据范围与提示

题中所有数据不超过 $2 \times 10^9$，保证方案序列的每个数字 $\leq n$。