← 返回题目列表

Codeforces · 2131/C

C. 使其相等

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

给定两个大小为 $$$n$$$ 的多重集 $$$S$$$ 和 $$$T$$$ 以及一个正整数 $$$k$$$,您可以对 $$$S$$$ 执行任意次数(包括零次)的以下操作:

  • 选择 $$$S$$$ 中的一个元素 $$$x$$$,并删除 $$$S$$$ 中出现的一个 $$$x$$$。然后,将 $$$x+k$$$ 插入 $$$S$$$ 中,或将 $$$|x-k|$$$ 插入 $$$S$$$ 中。

确定是否可以使 $$$S$$$ 等于 $$$T$$$。如果每个元素在 $$$S$$$ 和 $$$T$$$ 中出现的次数相同,则两个多重集 $$$S$$$ 和 $$$T$$$ 相等。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — 分别是 $$$S$$$ 的大小和常量。

第二行包含 $$$n$$$ 整数 $$$S_1,S_2,\ldots,S_n$$$ ($$$0 \le S_i \le 10^9$$$) — $$$S$$$ 中的元素。

第三行包含 $$$n$$$ 整数 $$$T_1,T_2,\ldots,T_n$$$ ($$$0 \le T_i \le 10^9$$$) — $$$T$$$ 中的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出“是“如果可以使$$$S$$$等于$$$T$$$,并且”NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

5
1 3
1
2
1 8
4
12
3 5
6 2 9
8 4 11
2 7
2 8
2 9
3 2
0 1 0
1 0 1

输出
复制

YES
YES
YES
NO
NO

注意

在第一个测试用例中,我们可以从 $$$S$$$ 中删除一次 $$$1$$$ 并将 $$$|1-k|=|1-3|=2$$$ 插入到 $$$S$$$ 中,使 $$$S$$$ 等于 $$$T$$$。

在第二个测试用例中,我们可以从 $$$S$$$ 中删除一次 $$$4$$$ 并将 $$$4+k=4+8=12$$$ 插入到 $$$S$$$ 中,使 $$$S$$$ 等于 $$$T$$$。

在最后一个测试用例中,我们可以证明$$$S$$$ 不可能等于$$$T$$$。