Problem Statement

Given two multisets $S$ and $T$ of size $n$ and a positive integer $k$, you may perform the following operations any number (including zero) of times on $S$:

• Select an element $x$ in $S$, and remove one occurrence of $x$ in $S$. Then, either insert $x+k$ into $S$, or insert $|x-k|$ into $S$.

Determine if it is possible to make $S$ equal to $T$. Two multisets $S$ and $T$ are equal if every element appears the same number of times in $S$ and $T$.

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $ 1 \le k \le 10^9$ ) — the size of $S$ and the constant, respectively.

The second line contains $n$ integers $S_1,S_2,\ldots,S_n$ ($0 \le S_i \le 10^9$) — the elements in $S$.

The third line contains $n$ integers $T_1,T_2,\ldots,T_n$ ($0 \le T_i \le 10^9$) — the elements in $T$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output “YES” if it is possible to make $S$ equal to $T$, and “NO” otherwise.

You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.

Solving

对于使用操作对集合间的相互转化，其转换对象不清晰时，考虑根据操作性质转化两集合元素为特征值，这样转化为两个集合为特征值集合，只要两个集合的特征值完全相同，则这两个集合可以相互转化。

在此题中，考虑操作对元素的「等效影响」是什么？需要找到一种统一规律，把 S 和 T 的元素映射到同一特征，若特征完全一致则可转换。

我们发现，无论怎么操作，元素最终会收敛到「与 k 相关的等效余数

所以我们可以根据其余数指定特征值，考虑对任意 x，其操作后的等效特征为 x % k 与 k - (x % k) 中的较小值（即「到 k 倍数的最短距离」），因为只要两个到k倍数的最短距离相同，这两个数一定可以互相转化

这样我们只需要比对两集合各个元素到k倍数的最短距离，即可得到答案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

void solve()
{  
    int n,k;
    cin >> n >> k;
    vector<int> s(n+1),t(n+1);
    for(int i=1;i<=n;i++) cin >> s[i];
    for(int i=1;i<=n;i++) cin >> t[i];
    // 转化为特征值
    auto check = [&](int x) -> int 
    {
        int r = x % k;
        if(r == 0) return 0;
        return min(r,k-r);
    };
    vector<int> ss,tt;
    for(int i=1;i<=n;i++)
    {
        ss.push_back(check(s[i]));
        tt.push_back(check(t[i]));
    }
    sort(ss.begin(),ss.end());
    sort(tt.begin(),tt.end());
    if(ss == tt) // 比较两集合的特征值
    {
        cout << "Yes\n";
    }
    else cout << "No\n";
}