Codeforces Round 950 (Div. 3) |
---|
Закончено |
У Софии был массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Однажды он ей надоел, поэтому она решила последовательно применить к нему $$$m$$$ операций изменения.
Каждая операция изменения описывается парой чисел $$$\langle c_j, d_j \rangle$$$ и означает, что надо присвоить элементу массива с индексом $$$c_j$$$ значение $$$d_j$$$, то есть выполнить присвоение $$$a_{c_j} = d_j$$$. После последовательного применения всех операций изменения София выкинула получившийся массив.
Недавно вы нашли массив из $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$. Вам интересно, является ли этот массив массивом Софии. Вам известны значения исходного массива, а также значения $$$d_1, d_2, \ldots, d_m$$$. Значения $$$c_1, c_2, \ldots, c_m$$$ оказались утерянными.
Существует ли такая последовательность $$$c_1, c_2, \ldots, c_m$$$, что последовательное применение операций изменения $$$\langle c_1, d_1, \rangle, \langle c_2, d_2, \rangle, \ldots, \langle c_m, d_m \rangle$$$ к массиву $$$a_1, a_2, \ldots, a_n$$$ превращает его в массив $$$b_1, b_2, \ldots, b_n$$$?
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следуют описания наборов.
В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер массива.
Во второй строке каждого набора даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы исходного массива.
В третьей строке каждого набора даны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — элементы найденного массива.
В четвёртой строке дано целое число $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — количество операций изменения.
В пятой строке даны $$$m$$$ целых чисел $$$d_1, d_2, \ldots, d_m$$$ ($$$1 \le d_j \le 10^9$$$) — сохранившееся значение для каждой операции изменения.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, аналогично сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выведите $$$t$$$ строк, каждая из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите «YES», если существует подходящая последовательность $$$c_1, c_2, \ldots, c_m$$$, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
731 2 11 3 241 3 1 241 2 3 52 1 3 522 357 6 1 10 103 6 1 11 1134 3 1143 1 7 82 2 7 10510 3 2 2 155 7 1 7 94 10 1 2 981 1 9 8 7 2 10 441000000000 203 203 203203 1000000000 203 10000000002203 100000000011151 3 4 5 1
YES NO NO NO YES NO YES
Название |
---|