CF1718D.Permutation for Burenka

We call an array $a$ pure if all elements in it are pairwise distinct. For example, an array $[1, 7, 9]$ is pure, $[1, 3, 3, 7]$ isn't, because $3$ occurs twice in it.

A pure array $b$ is similar to a pure array $c$ if their lengths $n$ are the same and for all pairs of indices $l$, $r$, such that $1 \le l \le r \le n$, it's true that $$\operatorname{argmax}([b_l, b_{l + 1}, \ldots, b_r]) = \operatorname{argmax}([c_l, c_{l + 1}, \ldots, c_r]),$$ where $\operatorname{argmax}(x)$ is defined as the index of the largest element in $x$ (which is unique for pure arrays). For example, $\operatorname{argmax}([3, 4, 2]) = 2$, $\operatorname{argmax}([1337, 179, 57]) = 1$.

Recently, Tonya found out that Burenka really likes a permutation $p$ of length $n$. Tonya decided to please her and give her an array $a$ similar to $p$. He already fixed some elements of $a$, but exactly $k$ elements are missing (in these positions temporarily $a_i = 0$). It is guaranteed that $k \ge 2$. Also, he has a set $S$ of $k - 1$ numbers.

Tonya realized that he was missing one number to fill the empty places of $a$, so he decided to buy it. He has $q$ options to buy. Tonya thinks that the number $d$ suits him, if it is possible to replace all zeros in $a$ with numbers from $S$ and the number $d$, so that $a$ becomes a pure array similar to $p$. For each option of $d$, output whether this number is suitable for him or not.

我们称一个数组 $a$ 是纯的，如果其中所有元素两两互不相同。例如，数组 $[1, 7, 9]$ 是纯的，而 $[1, 3, 3, 7]$ 不是纯的，因为 $3$ 在其中出现了两次。

两个纯数组 $b$ 和 $c$ 称为相似的，当且仅当它们长度 $n$ 相同，且对所有满足 $1 \le l \le r \le n$ 的下标对 $(l, r)$，均有

$$\operatorname{argmax}([b_l, b_{l + 1}, \ldots, b_r]) = \operatorname{argmax}([c_l, c_{l + 1}, \ldots, c_r]),$$

其中 $\operatorname{argmax}(x)$ 定义为 $x$ 中最大元素的下标（由于数组是纯的，该下标唯一）。例如，$\operatorname{argmax}([3, 4, 2]) = 2$，$\operatorname{argmax}([1337, 179, 57]) = 1$。

最近，Tonya 得知 Burenka 非常喜欢一个长度为 $n$ 的排列 $p$。Tonya 决定取悦她，送给她一个与 $p$ 相似的数组 $a$。他已预先固定了 $a$ 中的部分元素，但恰好有 $k$ 个位置缺失（这些位置暂时记为 $a_i = 0$）。题目保证 $k \ge 2$。此外，他还拥有一个大小为 $k - 1$ 的数集 $S$。

Tonya 意识到，他还缺少一个数来填满 $a$ 中所有空缺位置，于是决定购买它。他共有 $q$ 种购买选项。Tonya 认为一个数 $d$ 是合适的，当且仅当可以将 $a$ 中所有 $0$ 替换为 $S$ 中的数以及该数 $d$，使得最终得到的数组 $a$ 成为一个纯数组，且与 $p$ 相似。对每个候选数 $d$，请输出它是否合适。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) is the number of test cases. The description of the test cases follows.

The first line of each test case contains a couple of integers $n$ and $q$ ($1 \le n, q \le 3 \cdot 10^5$).

The second line of each input test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the permutation Burenka likes.

The third line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — elements of Tonya's array, where $0$ denotes a missing element. It is guaranteed that there are two indexes $i, j$ $(1 \le i, j \le n, i \ne j)$ such that $a_i = 0, a_j = 0$, which implies that $k \geq 2$.

The fourth line of each test case contains $k - 1$ distinct integers $s_1, s_2, \ldots, s_{k-1}$ ($1 \le s_i \le 10^6$) — elements of Tonya's set $S$.

Each of the next $q$ lines contains a single integer $d$ ($1 \le d \le 10^6$) — the number that Tonya plans to buy.

It is guaranteed that for each given $d$ it's possible to fill in the gaps in $a$ with numbers from $S$ and the number $d$ to get a pure array.

It is guaranteed that the sum of $n$ and the sum of $q$ in all tests does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）——即 Burenka 喜欢的排列。

每个测试用例的第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^6$）——即 Tonya 的数组，其中 $0$ 表示缺失的元素。保证存在两个下标 $i, j$（$1 \le i, j \le n,\, i \ne j$），使得 $a_i = 0$ 且 $a_j = 0$，即 $k \geq 2$。

每个测试用例的第四行包含 $k - 1$ 个互不相同的整数 $s_1, s_2, \ldots, s_{k-1}$（$1 \le s_i \le 10^6$）——即 Tonya 的集合 $S$ 中的元素。

接下来的 $q$ 行中，每行包含一个整数 $d$（$1 \le d \le 10^6$）——即 Tonya 计划购买的数字。

保证：对每个给定的 $d$，总能用集合 $S$ 中的数以及数字 $d$ 填补数组 $a$ 中的空缺，从而得到一个纯数组（pure array）。

保证：所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $3 \cdot 10^5$。

Output $q$ lines. For each value $d$, print "YES" if there is a way to fill the array $a$ to make it similar to $p$, and "NO" otherwise.

输出 $q$ 行。对于每个值 $d$，如果存在一种方式填充数组 $a$ 使其与 $p$ 相似，则输出 "YES"；否则输出 "NO"。

In the first test case for $d = 9$, you can get $a = [5, 9, 7, 6]$, it can be proved that $a$ is similar to $p$, for $d=1$ and $d=4$ it can be proved that there is no answer.

In the second test case for $d = 1$, you can get $a = [1, 5, 10, 9, 3]$, for $d = 8$, you can get $a = [3, 5, 10, 9, 8]$, it can be proved that for $d = 11$ there is no answer.

在第一个测试用例中，当 $d = 9$ 时，可得到 $a = [5, 9, 7, 6]$，可以证明该数组 $a$ 与 $p$ 相似；而当 $d = 1$ 和 $d = 4$ 时，可以证明不存在满足条件的解。

在第二个测试用例中，当 $d = 1$ 时，可得到 $a = [1, 5, 10, 9, 3]$；当 $d = 8$ 时，可得到 $a = [3, 5, 10, 9, 8]$；可以证明当 $d = 11$ 时不存在满足条件的解。