C2. Координация презентации (сложная версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В двух версиях отличаются ограничения на $$$q$$$ и ограничение по времени отличаются. В этой версии $$$0 \leq q \leq 2 \cdot 10^5$$$. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Команда, состоящая из $$$n$$$ участников, пронумерованных от $$$1$$$ до $$$n$$$, должна представить слайд-шоу на большом собрании. Слайд-шоу содержит $$$m$$$ слайдов.

Имеется массив $$$a$$$ длины $$$n$$$. Изначально участники собрания стоят в очереди в порядке $$$a_1, a_2, \ldots, a_n$$$ от начала до конца. Слайд-шоу состоит из последовательного показа слайдов с $$$1$$$ по $$$m$$$. Каждый слайд будет представлен участником, стоящим в начале очереди. После представления каждого слайда вы можете переместить участника, стоящего в начале очереди, на любую позицию в очереди (без изменения порядка остальных участников). Например, предположим, что очередь участников имеет вид $$$[\color{red}{3},1,2,4]$$$. После того как участник $$$3$$$ представит текущий слайд, вы можете изменить очередь участников на $$$[\color{red}{3},1,2,4]$$$, $$$[1,\color{red}{3},2,4]$$$, $$$[1,2,\color{red}{3},4]$$$ или $$$[1,2,4,\color{red}{3}]$$$.

Также имеется массив $$$b$$$ длины $$$m$$$. Слайд-шоу считается хорошим, если можно так перемещать участников после выступлений, чтобы слайд $$$i$$$ был представлен участником $$$b_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$m$$$.

Однако ваш назойливый начальник хочет сделать $$$q$$$ обновлений массива $$$b$$$. В $$$i$$$-м обновлении он выберет слайд $$$s_i$$$ и участника $$$t_i$$$ и присвоит $$$b_{s_i} := t_i$$$. Заметим, что эти обновления постоянны, то есть изменения, внесенные в массив $$$b$$$, будут применяться при обработке последующих обновлений.

Для каждого из $$$q+1$$$ состояний массива $$$b$$$ (начального состояния и после каждого из $$$q$$$ обновлений) определите, является ли слайд-шоу хорошим.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$0 \leq q \leq 2 \cdot 10^5$$$) — количество участников, количество слайдов и количество обновлений.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — начальный порядок расположения участников от начала до конца очереди. Гарантируется, что каждое целое число от $$$1$$$ до $$$n$$$ встречается в $$$a$$$ ровно один раз.

Третья строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le n$$$) — номера участников, которые должны представлять каждый слайд.

Каждая из следующих $$$q$$$ строк содержит по два целых числа $$$s_i$$$ и $$$t_i$$$ ($$$1 \le s_i \le m$$$, $$$1 \le t_i \le n$$$) — параметры обновления.

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

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

Для каждого набора входных данных выведите $$$q+1$$$ строку, соответствующих $$$q+1$$$ состоянию массива $$$b$$$. Выведите «YA», если слайд-шоу хорошее, и «TIDAK» в противном случае.

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «YA», «Ya», «ya» и «YA» будут распознаны как положительные ответы.

Пример
Входные данные
3
4 2 2
1 2 3 4
1 1
1 2
1 1
3 6 2
1 2 3
1 1 2 3 3 2
3 3
2 2
4 6 2
3 1 4 2
3 1 1 2 3 4
3 4
4 2
Выходные данные
YA
TIDAK
YA
YA
TIDAK
YA
TIDAK
YA
YA
Примечание

В первом наборе входных данных изначально вам не нужно перемещать участников, так как оба слайда будут представлены участником $$$1$$$, который уже находится в начале очереди. После этого присваивается $$$b_1 := 2$$$, теперь слайд $$$1$$$ должен быть представлен участником $$$2$$$. Это невозможно, так как участник $$$1$$$ представит слайд $$$1$$$ первым. Затем устанавливается $$$b_1 = 1$$$, $$$b$$$ становится таким же, как и начальный $$$b$$$, что делает слайд-шоу хорошим.