Codeforces Round 805 (Div. 3) |
---|
Закончено |
Мультимножество — это такой набор чисел, в котором могут быть равные элементы, а порядок чисел не имеет значение. Два мультимножества равны, когда каждое значение встречается в них одинаковое количество раз. Например, мультимножества $$$\{2,2,4\}$$$ и $$$\{2,4,2\}$$$ равны, но мультимножества $$$\{1,2,2\}$$$ и $$$\{1,1,2\}$$$ — нет.
Вам даны два мультимножества $$$a$$$ и $$$b$$$, каждое состоит из $$$n$$$ целых чисел.
За одну операцию можно любой элемент мультимножества $$$b$$$ увеличить в два раза или уменьшить в два раза (с округлением вниз). Другими словами, вам доступна одна из следующих операций для элемента $$$x$$$ из мультимножества $$$b$$$:
Обратите внимание, что изменять элементы мультимножества $$$a$$$ нельзя.
Проверьте, можно ли за произвольное количество операций (возможно, $$$0$$$) сделать так, чтобы мультимножество $$$b$$$ стало равно мультимножеству $$$a$$$.
Например, если $$$n = 4$$$, $$$a = \{4, 24, 5, 2\}$$$, $$$b = \{4, 1, 6, 11\}$$$, то ответ положительный. Можно действовать следующим образом:
В первой строке входных данных задано единственное целое число $$$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 и NO в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
542 4 5 241 4 6 1131 4 174 5 3154 7 10 13 142 14 14 26 4252 2 4 4 428 46 62 71 9861 2 10 16 64 8020 43 60 74 85 99
YES NO YES YES YES
Первый пример разобран в условии.
Во втором примере невозможно получить значение $$$31$$$ из чисел мультимножества $$$b$$$ доступными операциями.
В третьем примере можно действовать следующим образом:
Название |
---|