Equate Multisets

题意翻译

多重集是一种特殊的集合，其元素可以重复，并且，和集合一样，元素的顺序不重要。如果两个多重集中，每个元素的出现次数都一样，那么这两个多重集就是相等的。 如，$\{2, 2, 4\}$ 和 $\{2, 4, 2\}$ 是相同的。而 $\{1, 2, 2\}$ 和 $\{1, 1, 2\}$ 不是相同的。 现在给你两个多重集 $a$ 和 $b$，每个包含 $n (1 \le 2\cdot 10^5)$ 个整数。 在一次操作中，$b$ 中的一个元素可以被翻倍或是减半（向下取整）。或者说，对于一个 $b$ 中的元素 $x$，你可以做下面两种操作。 - 替换 $x$ 为 $2x$ - 替换 $x$ 为 $\lfloor \frac{x}{2} \rfloor$ 注意你不能对多重集 $a$ 做任何操作。 请问你是否能使多重集 $b$ 在经过任意数量的操作后和 $a$ 相等（也可以是 $0$ 个操作）。 由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译。

题目描述

Multiset —is a set of numbers in which there can be equal elements, and the order of the numbers does not matter. Two multisets are equal when each value occurs the same number of times. For example, the multisets $ \{2,2,4\} $ and $ \{2,4,2\} $ are equal, but the multisets $ \{1,2,2\} $ and $ \{1,1,2\} $ — are not. You are given two multisets $ a $ and $ b $ , each consisting of $ n $ integers. In a single operation, any element of the $ b $ multiset can be doubled or halved (rounded down). In other words, you have one of the following operations available for an element $ x $ of the $ b $ multiset: - replace $ x $ with $ x \cdot 2 $ , - or replace $ x $ with $ \lfloor \frac{x}{2} \rfloor $ (round down). Note that you cannot change the elements of the $ a $ multiset. See if you can make the multiset $ b $ become equal to the multiset $ a $ in an arbitrary number of operations (maybe $ 0 $ ). For example, if $ n = 4 $ , $ a = \{4, 24, 5, 2\} $ , $ b = \{4, 1, 6, 11\} $ , then the answer is yes. We can proceed as follows: - Replace $ 1 $ with $ 1 \cdot 2 = 2 $ . We get $ b = \{4, 2, 6, 11\} $ . - Replace $ 11 $ with $ \lfloor \frac{11}{2} \rfloor = 5 $ . We get $ b = \{4, 2, 6, 5\} $ . - Replace $ 6 $ with $ 6 \cdot 2 = 12 $ . We get $ b = \{4, 2, 12, 5\} $ . - Replace $ 12 $ with $ 12 \cdot 2 = 24 $ . We get $ b = \{4, 2, 24, 5\} $ . - Got equal multisets $ a = \{4, 24, 5, 2\} $ and $ b = \{4, 2, 24, 5\} $ .

输入输出格式

输入格式

The first line of input data contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) —the number of test cases. Each test case consists of three lines. The first line of the test case contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) —the number of elements in the multisets $ a $ and $ b $ . The second line gives $ n $ integers: $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9 $ ) —the elements of the multiset $ a $ . Note that the elements may be equal. The third line contains $ n $ integers: $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_1 \le b_2 \le \dots \le b_n \le 10^9 $ ) — elements of the multiset $ b $ . Note that the elements may be equal. It is guaranteed that the sum of $ n $ values over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print on a separate line: - YES if you can make the multiset $ b $ become equal to $ a $ , - NO otherwise. You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive answer).

输入输出样例

输入样例 #1

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

输出样例 #1

YES
NO
YES
YES
YES

说明

The first example is explained in the statement. In the second example, it is impossible to get the value $ 31 $ from the numbers of the multiset $ b $ by available operations. In the third example, we can proceed as follows: - Replace $ 2 $ with $ 2 \cdot 2 = 4 $ . We get $ b = \{4, 14, 14, 26, 42\} $ . - Replace $ 14 $ with $ \lfloor \frac{14}{2} \rfloor = 7 $ . We get $ b = \{4, 7, 14, 26, 42\} $ . - Replace $ 26 $ with $ \lfloor \frac{26}{2} \rfloor = 13 $ . We get $ b = \{4, 7, 14, 13, 42\} $ . - Replace $ 42 $ with $ \lfloor \frac{42}{2} \rfloor = 21 $ . We get $ b = \{4, 7, 14, 13, 21\} $ . - Replace $ 21 $ with $ \lfloor \frac{21}{2} \rfloor = 10 $ . We get $ b = \{4, 7, 14, 13, 10\} $ . - Got equal multisets $ a = \{4, 7, 10, 13, 14\} $ and $ b = \{4, 7, 14, 13, 10\} $ .

题意翻译

多重集是一种特殊的集合，其元素可以重复，并且，和集合一样，元素的顺序不重要。如果两个多重集中，每个元素的出现次数都一样，那么这两个多重集就是相等的。 如，$\{2, 2, 4\}$ 和 $\{2, 4, 2\}$ 是相同的。而 $\{1, 2, 2\}$ 和 $\{1, 1, 2\}$ 不是相同的。 现在给你两个多重集 $a$ 和 $b$，每个包含 $n (1 \le 2\cdot 10^5)$ 个整数。 在一次操作中，$b$ 中的一个元素可以被翻倍或是减半（向下取整）。或者说，对于一个 $b$ 中的元素 $x$，你可以做下面两种操作。 - 替换 $x$ 为 $2x$ - 替换 $x$ 为 $\lfloor \frac{x}{2} \rfloor$ 注意你不能对多重集 $a$ 做任何操作。 请问你是否能使多重集 $b$ 在经过任意数量的操作后和 $a$ 相等（也可以是 $0$ 个操作）。 由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译。