C2. Равные мультимножества (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии массив $$$a$$$ может быть любым. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Дан массив $$$a$$$ размера $$$n$$$ и параметр $$$k$$$. Массив $$$b$$$ называется хорошим, если выполняется следующее условие:

  • Для каждого $$$i$$$ от $$$k$$$ до $$$n$$$ массив $$$[a_{i-k+1},a_{i-k+2},\ldots,a_i]$$$ является перестановкой массива $$$[b_{i-k+1},b_{i-k+2},\ldots,b_i]$$$.

Вам даны два массива $$$a$$$ и $$$b$$$ размера $$$n$$$, а также целое число $$$k$$$. Массив $$$a$$$ содержит числа от $$$1$$$ до $$$n$$$. Массив $$$b$$$ содержит только целые числа от $$$1$$$ до $$$n$$$ и $$$-1$$$.

Определите, можно ли заменить все $$$-1$$$ в $$$b$$$ на целые числа от $$$1$$$ до $$$n$$$ так, чтобы массив $$$b$$$ был хорошим относительно $$$k$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq n$$$ или $$$b_i=-1$$$).

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

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

Для каждого набора входных данных выведите YES, если это возможно, и NO в противном случае. Буквы можно выводить в любом регистре.

Пример
Входные данные
5
5 5
1 2 3 4 5
3 1 5 2 4
5 2
1 2 1 2 1
2 -1 -1 -1 -1
6 1
5 6 2 2 4 3
5 -1 -1 2 -1 3
2 1
1 2
2 -1
6 4
1 2 3 4 1 2
2 -1 3 -1 4 -1
Выходные данные
YES
YES
YES
NO
NO
Примечание

В первом наборе входных данных $$$k=5$$$. Единственный подмассив размера $$$5$$$ — это $$$[1,5]$$$. Можно видеть, что $$$b$$$ является перестановкой массива $$$a$$$, поэтому ответ равен YES.

Во втором наборе входных данных можно взять $$$b=[2,1,2,1,2]$$$. Видно, что каждое окно размером $$$2$$$ как в $$$a$$$, так и в $$$b$$$ имеет вид либо $$$[1,2]$$$, либо $$$[2,1]$$$, что является перестановками друг друга, поэтому ответ —YES.

В четвёртом наборе входных данных, поскольку $$$a_1 \neq b_1$$$ и $$$k=1$$$, ответ — NO.