D. Перестановка для Бурёнки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив $$$a$$$ чистым, если в нем все элементы попарно различны. Например, массив $$$[1, 7, 9]$$$ — чистый, а $$$[1, 3, 3, 7]$$$ — нет, ведь $$$3$$$ встречается в нем дважды.

Чистый массив $$$b$$$ похож на чистый массив $$$c$$$, если их длина $$$n$$$ одинакова, и для всех пар индексов $$$l$$$, $$$r$$$ таких, что $$$1 \le l \le r \le n$$$, выполняется $$$$$$\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$$$.

Недавно Тоня узнал, что Бурёнке очень нравится перестановка $$$p$$$ длины $$$n$$$. Тоня решил обрадовать Бурёнку и подарить ей массив $$$a$$$, похожий на $$$p$$$. Он уже зафиксировал некоторые элементы $$$a$$$, но ровно $$$k$$$ элементов отсутствуют (в этих позициях сейчас $$$a_i = 0$$$). Гарантируется, что $$$k \ge 2$$$. Кроме того, у Тони есть множество $$$S$$$ из $$$k - 1$$$ числа.

Тоня понял, что для того, чтобы заполнить пропуски в массиве $$$a$$$ ему не хватает одного числа, поэтому он решил купить его. У него есть $$$q$$$ вариантов покупки. Тоня считает, что число $$$d$$$ подходит ему, если можно заполнить пропуски в $$$a$$$ числами из $$$S$$$ и числом $$$d$$$ так, чтобы $$$a$$$ стал чистым массивом, похожим на $$$p$$$. Для каждого варианта покупки числа $$$d$$$ выведите, подходит ли Тоне это число или нет.

Входные данные

В первой строке находится единственное целое число $$$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$$$) — перестановка, которая нравится Бурёнке.

В третьей строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — элементы массива, где $$$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$$$) — числа, которые есть у Тони во множестве $$$S$$$.

Каждая из следующих $$$q$$$ строк содержит одно целое число $$$d$$$ ($$$1 \le d \le 10^6$$$) – число, которое планирует купить Тоня.

Гарантируется, что для каждого данного $$$d$$$ существует способ заполнить пропуски в $$$a$$$ числами из $$$S$$$ и числом $$$d$$$ так, чтобы получить чистый массив.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем тестам не превосходят $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ строк. Для каждого значения $$$d$$$ выведите «YES», если существует способ заполнить массив $$$a$$$, сделав его похожим на $$$p$$$, и «NO» в противном случае.

Пример
Входные данные
4
4 3
1 4 3 2
5 0 7 0
6
9
1
4
5 3
1 2 5 4 3
0 5 10 0 0
3 9
1
8
11
5 2
1 4 3 2 5
0 0 0 0 0
7 9 1 5
6
100
4 2
4 1 3 2
0 5 3 0
2
4
6
Выходные данные
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
Примечание

В первом наборе входных данных для $$$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$$$ ответа не существует.