F. Уравняй мультимножества
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мультимножество — это такой набор чисел, в котором могут быть равные элементы, а порядок чисел не имеет значение. Два мультимножества равны, когда каждое значение встречается в них одинаковое количество раз. Например, мультимножества $$$\{2,2,4\}$$$ и $$$\{2,4,2\}$$$ равны, но мультимножества $$$\{1,2,2\}$$$ и $$$\{1,1,2\}$$$ — нет.

Вам даны два мультимножества $$$a$$$ и $$$b$$$, каждое состоит из $$$n$$$ целых чисел.

За одну операцию можно любой элемент мультимножества $$$b$$$ увеличить в два раза или уменьшить в два раза (с округлением вниз). Другими словами, вам доступна одна из следующих операций для элемента $$$x$$$ из мультимножества $$$b$$$:

  • либо заменить $$$x$$$ на $$$x \cdot 2$$$,
  • либо заменить $$$x$$$ на $$$\lfloor \frac{x}{2} \rfloor$$$ (округление вниз).

Обратите внимание, что изменять элементы мультимножества $$$a$$$ нельзя.

Проверьте, можно ли за произвольное количество операций (возможно, $$$0$$$) сделать так, чтобы мультимножество $$$b$$$ стало равно мультимножеству $$$a$$$.

Например, если $$$n = 4$$$, $$$a = \{4, 24, 5, 2\}$$$, $$$b = \{4, 1, 6, 11\}$$$, то ответ положительный. Можно действовать следующим образом:

  • Заменим $$$1$$$ на $$$1 \cdot 2 = 2$$$. Получим $$$b = \{4, 2, 6, 11\}$$$.
  • Заменим $$$11$$$ на $$$\lfloor \frac{11}{2} \rfloor = 5$$$. Получим $$$b = \{4, 2, 6, 5\}$$$.
  • Заменим $$$6$$$ на $$$6 \cdot 2 = 12$$$. Получим $$$b = \{4, 2, 12, 5\}$$$.
  • Заменим $$$12$$$ на $$$12 \cdot 2 = 24$$$. Получим $$$b = \{4, 2, 24, 5\}$$$.
  • получили равные мультимножества $$$a = \{4, 24, 5, 2\}$$$ и $$$b = \{4, 2, 24, 5\}$$$.
Входные данные

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

Каждый набор входных данных состоит из трех строк.

В первой строке набора задано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в мультимножествах $$$a$$$ и $$$b$$$.

Во второй строке даны $$$n$$$ целых чисел: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$) — элементы набора $$$a$$$. Обратите внимание, что среди элементов могут быть равные.

В третьей строке даны $$$n$$$ целых чисел: $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_n \le 10^9$$$) — элементы набора $$$b$$$. Обратите внимание, что среди элементов могут быть равные.

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

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

Для каждого набора входных данных в отдельной строке выведите:

  • YES, если можно сделать так, чтобы мультимножество $$$b$$$ стало равно $$$a$$$,
  • NO в противном случае.

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

Пример
Входные данные
5
4
2 4 5 24
1 4 6 11
3
1 4 17
4 5 31
5
4 7 10 13 14
2 14 14 26 42
5
2 2 4 4 4
28 46 62 71 98
6
1 2 10 16 64 80
20 43 60 74 85 99
Выходные данные
YES
NO
YES
YES
YES
Примечание

Первый пример разобран в условии.

Во втором примере невозможно получить значение $$$31$$$ из чисел мультимножества $$$b$$$ доступными операциями.

В третьем примере можно действовать следующим образом:

  • Заменим $$$2$$$ на $$$2 \cdot 2 = 4$$$. Получим $$$b = \{4, 14, 14, 26, 42\}$$$.
  • Заменим $$$14$$$ на $$$\lfloor \frac{14}{2} \rfloor = 7$$$. Получим $$$b = \{4, 7, 14, 26, 42\}$$$.
  • Заменим $$$26$$$ на $$$\lfloor \frac{26}{2} \rfloor = 13$$$. Получим $$$b = \{4, 7, 14, 13, 42\}$$$.
  • Заменим $$$42$$$ на $$$\lfloor \frac{42}{2} \rfloor = 21$$$. Получим $$$b = \{4, 7, 14, 13, 21\}$$$.
  • Заменим $$$21$$$ на $$$\lfloor \frac{21}{2} \rfloor = 10$$$. Получим $$$b = \{4, 7, 14, 13, 10\}$$$.
  • получили равные мультимножества $$$a = \{4, 7, 10, 13, 14\}$$$ и $$$b = \{4, 7, 14, 13, 10\}$$$.