#CF2131C. 使它们相等

使它们相等

C. 使它们相等

每次测试的时间限制:2 秒
每次测试的内存限制:256 兆字节

给定两个大小为 nn 的多重集 SSTT,以及一个正整数 kk。你可以对 SS 执行以下操作任意次(包括零次):

  • 选择 SS 中的一个元素 xx,移除 xx 的一个出现。然后,要么将 x+kx+k 插入 SS 中,要么将 xk|x-k| 插入 SS 中。

判断是否有可能使 SS 等于 TT
两个多重集 SSTT 相等,如果每个元素在 SSTT 中出现的次数相同。

输入
每个测试包含多个测试用例。第一行包含一个整数 tt1t1041 \le t \le 10^4)——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 nnkk1n21051 \le n \le 2 \cdot 10^51k1091 \le k \le 10^9)—— SS 的大小和常数。

第二行包含 nn 个整数 S1,S2,,SnS_1, S_2, \dots, S_n0Si1090 \le S_i \le 10^9)—— SS 中的元素。

第三行包含 nn 个整数 T1,T2,,TnT_1, T_2, \dots, T_n0Ti1090 \le T_i \le 10^9)—— TT 中的元素。

保证所有测试用例的 nn 之和不超过 21052 \cdot 10^5

输出
对于每个测试用例,如果可以使 SS 等于 TT,输出 "YES",否则输出 "NO"

你可以以任何大小写输出答案(例如 "yEs""yes""Yes""YES" 都会被识别为肯定回答)。

示例
输入

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

说明
在第一个测试用例中,我们可以移除 SS 中的一个 11,并将 1k=13=2|1 - k| = |1 - 3| = 2 插入 SS,使得 SS 等于 TT

在第二个测试用例中,我们可以移除 SS 中的一个 44,并将 4+k=4+8=124 + k = 4 + 8 = 12 插入 SS,使得 SS 等于 TT

在最后一个测试用例中,可以证明无法使 SS 等于 TT