P5826 [Template] Subsequence Automaton.

In this problem, if $x$ is a subsequence of $y$, then it is equivalent to the existence of a **strictly increasing** sequence $z$ such that $|z| = |x|$, $z_{|x|} \leq |y|$, and $\forall i \in [1, ~|x|],~y_{z_i} = x_i$. Here $|x|,~|y|,~|z|$ denote the lengths of sequences $x,~y,~z$, and $x_i,~y_i,~z_i$ denote the $i$-th element of sequences $x,~y,~z$. This problem was rejected in the backup problem set of ``yLOI2020``.

Given a positive integer sequence $a$ of length $n$, there are $q$ queries. In the $i$-th query, a sequence $b_i$ of length $L_i$ is given. You need to determine whether $b_i$ is a subsequence of $a$. All elements in sequence $a$ and all $b_i$ are no greater than a given positive integer $m$.

Each test case contains exactly one dataset. The first line contains four integers separated by spaces: $type,~n,~q,~m$. Here $type$ indicates the subtask number of the test point, and the meanings of the other variables are the same as in the Description. The second line contains $n$ integers separated by spaces. The $i$-th number is the $i$-th element $a_i$ of sequence $a$. Lines $3$ to $(q + 2)$ each represent a query. The input format of line $(i + 2)$ is: - At the beginning of line $(i + 2)$ there is an integer $l_i$, which is the length of the sequence in the $i$-th query. After one space, there are $l_i$ integers separated by spaces. The $(j + 1)$-th integer on this line is the $j$-th element $b_{i, j}$ of sequence $b_i$.

For each query, output one string per line. If the given sequence is a subsequence of $a$, output `Yes`; otherwise output `No`.

#### Explanation for Sample 1 - For the first query, there is no $5$ in the original sequence, so the given sequence is obviously not a subsequence of the original sequence. - For the second query, there are two valid sequences $z$, which are $\{2,~3\}$ and $\{2,~4\}$. That is, $a_{2} = b_{2, 1},~a_3 = b_{2, 2}$ or $a_2 = b_{2, 1},~a_{4} = b_{2, 2}$. Here $b_{i, j}$ denotes the $j$-th element of sequence $b_i$. The meaning of sequence $z$ is given in the Background, and the same below. - For the third query, there is no valid sequence $z$. - For the fourth query, there are two valid sequences $z$, which are $\{1,~3,~5\}$ and $\{1,~4,~5\}$. - For the fifth query, there is one valid sequence $z$, which is $\{1,~2,~3,~4,~5\}$. #### Constraints and Conventions **This problem uses bundled multi-point testing, with a total of 3 subtasks**. - 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$. For all test points, it is guaranteed that $1 \leq n, m, q \leq 10^5$, $1 \leq a_i, b_{i, j} \leq m$, $1 \leq l_i \leq 10^6$, and $\sum_{i = 1}^{q} l_i \leq 10^6$. ### Notes - Please pay attention to the impact of constant factors on program efficiency. - The input size of this problem is large, so please pay attention to input reading efficiency. - Please note that in the first line of input, the order is to input the number of queries $q$ first, and then the maximum value $m$ of sequence elements. Translated by ChatGPT 5