Назовем массив \(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» в противном случае.
Примечание
В первом наборе входных данных для \(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\) ответа не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|