Background

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.

Problem Description

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$.

Input Format

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$.

Output Format

For each query, output one string per line. If the given sequence is a subsequence of $a$, output Yes; otherwise output 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

Hint

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