【模板】子序列自动机

本题中，若 $x$ 是 $y$ 的子序列，则等价于存在一个**单调递增**序列 $z$，满足 $|z| = |x|$，$z_{|x|} \leq |y|$，且 $\forall i \in [1, ~|x|],~y_{z_i} = x_i$。其中 $|x|,~|y|,~|z|$ 分别代表序列 $x,~y,~z$ 的长度，$x_i,~y_i,~z_i$ 分别代表序列 $x,~y,~z$ 的第 $i$ 项。 这是一道在 ``yLOI2020`` 备选题里被毙掉的题目。

给定一个长度为 $n$ 的正整数序列 $a$ ，有 $q$ 次询问，第 $i$ 次询问给定一个长度为 $L_i$ 的序列 $b_i$，请你判断 $b_i$ 是不是 $a$ 的子序列。序列 $a$ 和所有 $b_i$ 中的元素都不大于一个给定的正整数 $m$。

每个测试点有且仅有一组数据。 输入的第一行是四个用空格隔开的整数，分别代表 $type,~n,~q,~m$。其中 $type$ 代表测试点所在的子任务编号，其余变量的含义见【题目描述】。 输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个数字代表序列 $a$ 的第 $i$ 个元素 $a_i$。 第 $3$ 行至第 $(q + 2)$ 行，每行代表一次询问。第 $(i + 2)$ 行的输入格式为： - 第 $(i + 2)$ 行的行首有一个整数 $l_i$，代表第 $i$ 次询问的序列长度。一个空格后有 $l_i$ 个用空格隔开的整数。该行的第 $(j + 1)$ 个整数代表序列 $b_i$ 的第 $j$ 个元素 $b_{i, j}$。

对于每次询问，输出一行一个字符串，若给定的序列是 $a$ 的子序列，则输出 `Yes`，否则输出 `No`。

0 5 5 5
1 3 2 2 4
3 1 5 2
2 3 2
3 1 2 3
3 1 2 4
5 1 3 2 2 4

No
Yes
No
Yes
Yes

#### 样例 1 解释 - 对于第一次询问，原序列中没有 $5$，所以给定序列显然不是原序列的子序列。 - 对于第二次询问，存在两个合法的序列 $z$，分别是 $\{2,~3\}$ 和 $\{2,~4\}$。即 $a_{2} = b_{2, 1},~a_3 = b_{2, 2}$ 或 $a_2 = b_{2, 1},~a_{4} = b_{2, 2}$。这里 $b_{i, j}$ 代表序列 $b_i$ 的第 $j$ 个元素，序列 $z$ 的含义见【题目背景】，下同。 - 对于第三次询问，不存在合法的序列 $z$。 - 对于第四次询问，存在两个合法的序列 $z$，分别是 $\{1,~3,~5\}$ 和 $\{1,~4,~5\}$。 - 对于第五次询问，存在一个合法的序列 $z$，为 $\{1,~2,~3,~4,~5\}$。 #### 数据范围与约定 **本题采用多测试点捆绑测试，共有 3 个子任务**。 - Subtask 1（20 points）：$type = 1$，$n, q, m \leq 100$，$\sum_{i = 1}^{q} l_i \leq 10^3$。 - Subtask 2（35 points）：$type = 2$，$n,q \leq 10^5$，$m \leq 26$，$\sum_{i = 1}^{q} l_i \leq 10^6$。 - Subtask 3（45 points）：$type = 3$，$n,q,m \leq 10^5$，$\sum_{i = 1}^q L_i \leq 10^6$。 对于全部的测试点，保证 $1 \leq n, m, q \leq 10^5$，$1 \leq a_i, b_{i, j} \leq m$，$1 \leq l_i \leq 10^6$，$\sum_{i = 1}^{q} l_i \leq 10^6$。 ### 提示 - 请注意常数因子对程序效率造成的影响。 - 本题输入规模较大，请注意数据读入对程序效率造成的影响。 - 请注意输入第一行的顺序为先输入询问次数 $q$，再输入序列元素最大值 $m$。