← 返回题目列表

Codeforces · 1702/F

F. 等于多重集

中文机器翻译题面 查看原题

多重集 - 是一组数字,其中可以有相等的元素,并且数字的顺序并不重要。当每个值出现相同次数时,两个多重集相等。例如,多重集 $$$\{2,2,4\}$$$ 和 $$$\{2,4,2\}$$$ 相等,但多重集 $$$\{1,2,2\}$$$ 和 $$$\{1,1,2\}$$$ — 则不同。

给你两个多重集 $$$a$$$ 和 $$$b$$$,每个都由 $$$n$$$ 整数组成。

在单个操作中,$$$b$$$ 多重集的任何元素都可以加倍或减半(向下舍入)。换句话说,您可以对 $$$b$$$ 多重集的元素 $$$x$$$ 使用以下操作之一:

- 将 $$$x$$$ 替换为 $$$x \cdot 2$$$,
- 或将 $$$x$$$ 替换为 $$$\lfloor \frac{x}{2} \rfloor$$$ (向下舍入)。

请注意,您无法更改 $$$a$$$ 多重集的元素。

看看是否可以在任意次数的操作中使多重集 $$$b$$$ 变得等于多重集 $$$a$$$(可能是 $$$0$$$)。

例如,如果 $$$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$$$。

输出

对于每个测试用例,在单独的行上打印:

- 是,如果你可以使多重集 $$$b$$$ 等于 $$$a$$$,
- 否则不。

任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定答案)。

示例

输入 #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

注意

第一个示例在语句中进行了解释。

在第二个示例中,无法通过可用操作从多重集 $$$b$$$ 的数字中获取值 $$$31$$$。

在第三个示例中,我们可以按如下方式进行:

- 将 $$$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\}$$$。