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\} $ .

题目大意：
多重集是一种特殊的集合，其中的元素可以重复，并且元素的顺序不重要。如果两个多重集中，每个元素的出现次数都一样，那么这两个多重集就是相等的。给你两个多重集a和b，每个包含n个整数。在一次操作中，b中的一个元素可以被翻倍或者减半（向下取整）。问是否能使多重集b在经过任意数量的操作后和a相等（也可以是0个操作）。

输入输出数据格式：
输入数据的第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例由三行组成。
测试用例的第一行包含一个整数n（1≤n≤2*10^5）——多重集a和b的元素数量。
测试用例的第二行给出n个整数：a1,a2,…,an（1≤a1≤a2≤…≤an≤10^9）——多重集a的元素。注意元素可能相等。
测试用例的第三行包含n个整数：b1,b2,…,bn（1≤b1≤b2≤…≤bn≤10^9）——多重集b的元素。注意元素可能相等。
保证所有测试用例的n值总和不超过2*10^5。

对于每个测试用例，输出一行：
- 如果可以使多重集b变为a，则输出YES；
- 否则输出NO。
输出YES和NO时大小写不敏感。题目大意： 多重集是一种特殊的集合，其中的元素可以重复，并且元素的顺序不重要。如果两个多重集中，每个元素的出现次数都一样，那么这两个多重集就是相等的。给你两个多重集a和b，每个包含n个整数。在一次操作中，b中的一个元素可以被翻倍或者减半（向下取整）。问是否能使多重集b在经过任意数量的操作后和a相等（也可以是0个操作）。 输入输出数据格式： 输入数据的第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例由三行组成。 测试用例的第一行包含一个整数n（1≤n≤2*10^5）——多重集a和b的元素数量。 测试用例的第二行给出n个整数：a1,a2,…,an（1≤a1≤a2≤…≤an≤10^9）——多重集a的元素。注意元素可能相等。 测试用例的第三行包含n个整数：b1,b2,…,bn（1≤b1≤b2≤…≤bn≤10^9）——多重集b的元素。注意元素可能相等。 保证所有测试用例的n值总和不超过2*10^5。 对于每个测试用例，输出一行： - 如果可以使多重集b变为a，则输出YES； - 否则输出NO。 输出YES和NO时大小写不敏感。