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

Борис думает, что шахматы это скучная игра, поэтому он ушел со своего турнира пораньше. Он пошел в парикмахерскую, ведь его прическа была немного неаккуратная.

В настоящий момент его волосы можно описать массивом $$$a_1,a_2,\ldots, a_n$$$, где $$$a_i$$$ — высота волоса на позиции $$$i$$$. Его желаемая прическа описывается массивом $$$b_1,b_2,\ldots, b_n$$$ аналогично.

У парикмахера есть $$$m$$$ бритв. Каждая бритва имеет некоторый размер и может быть использована не более одного раза. За одну операцию парикмахер может выбрать одну бритву и обрезать с помощью нее отрезок волос Бориса. Формально, операция выглядит следующим образом:

  • Выбрать ранее неиспользованную бритву, пусть ее размер равен $$$x$$$;
  • Выбрать отрезок $$$[l,r]$$$ ($$$1\leq l \leq r \leq n$$$);
  • Присвоить $$$a_i := \min (a_i,x)$$$ для всех $$$l\leq i \leq r$$$.

Обратите внимание, что некоторые бритвы могут иметь одинаковый размер. Парикмахер может выбирать размер $$$x$$$ максимум столько раз, сколько у него есть бритв размера $$$x$$$.

Парикмахер может выполнить сколько угодно операций, не используя одну бритву дважды. Необходимо, чтобы в конце выполнялось $$$a_i = b_i$$$ для всех $$$1 \leq i \leq n$$$. Он не обязан использовать все бритвы.

Определите, может ли парикмахер сделать необходимую Борису стрижку.

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

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

Первая строка каждого набора входных данных содержит положительное целое число $$$n$$$ ($$$3\leq n\leq 2\cdot 10^5$$$) — длину массивов $$$a$$$ и $$$b$$$.

Вторая строка содержит $$$n$$$ положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — описание текущих волос Бориса.

Третья строка содержит $$$n$$$ положительных целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — описание необходимой стрижки.

Четвертая строка содержит положительное целое число $$$m$$$ ($$$1 \leq m \leq 2\cdot 10^5$$$) — количество бритв.

Пятая строка содержит $$$m$$$ положительных целых чисел $$$x_1,x_2, \ldots, x_m$$$ ($$$1 \leq x_i \leq 10^9$$$) — размеры бритв.

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

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

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

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
7
3
3 3 3
2 1 2
2
1 2
6
3 4 4 6 3 4
3 1 2 3 2 3
3
3 2 3
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
3
1 1 1
1 1 2
12
4 2 4 3 1 5 6 3 5 6 2 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
8
1 5 3 5 4 2 3 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
7
1 5 3 4 2 3 1
3
19747843 2736467 938578397
2039844 2039844 2039844
1
2039844
Выходные данные
YES
NO
YES
NO
YES
NO
YES
Примечание

В первом примере волосы Бориса изначально равны $$$[3,3,3]$$$. Опишем последовательность из $$$2$$$ операций, которые может выполнить парикмахер:

  • Использовать бритву размера $$$1$$$ на отрезке $$$[2,2]$$$; волосы становятся $$$[3,1,3]$$$.
  • Использовать бритву размера $$$2$$$ на отрезке $$$[1,3]$$$; волосы становятся $$$[2,1,2]$$$, что и требуется.

В третьем примере можно ничего не делать, так как волосы уже в желаемом состоянии.

В четвертом примере нельзя обрезать волосы так, чтобы их длина увеличилась, и $$$[1,1,1]$$$ превратился в $$$[1,1,2]$$$.