Make it Equal

We need decide whether each element of $S$ can be independently transformed so that the final multiset becomes $T$.

The important word is independently. Operations only replace one number with another number. They never split, merge, copy, or delete elements. So this is really asking:

For each number, what set of numbers can it reach?

Then we just compare how many elements from each reachable “type” appear in $S$ and $T$.

Understanding The Operation

From a number $x$, we may replace it with either:

$x+k$

or

$|x-k|$

If $x \ge k$, then:

$|x-k| = x-k$

So for large enough values, we can move by $+k$ or $-k$. That means the remainder modulo $k$ stays the same.

Example with $k=5$:

$17 \to 12 \to 7 \to 2$

All of these are congruent to $2 \pmod 5$.

So far, this screams “compare modulo $k$”. But there is one catch.

The Catch: Small Numbers Reflect

If $0 \le x < k$, then:

$|x-k| = k-x$

So a small remainder $r$ can become $k-r$.

For example, if $k=5$:

$2 \to |2-5| = 3$

So remainder $2$ and remainder $3$ are connected.

More generally, if a number has remainder $r$, we can reduce it down to $r$ by subtracting $k$ repeatedly. Then from $r$, we can go to $k-r$.

That means remainder $r$ and remainder $k-r$ are in the same reachable group.

Reachability Class

For a number $x$, let:

$r = x \bmod k$

The number can reach values whose remainders are either:

$r$

or

$k-r$

So the whole reachable class can be represented by:

$\min(r, k-r)$

This works nicely for edge cases too:

• If $r=0$, then $\min(0,k)=0$.
• If $k$ is even and $r=k/2$, then $r=k-r$, so it maps to itself.

This canonical value is the only thing that matters.

Why Comparing Buckets Is Enough

Suppose an element of $S$ has canonical value $c$. It can only ever become numbers with the same canonical value $c$.

So if $S$ has three elements in bucket $c=2$, then $T$ must also have exactly three elements in bucket $c=2$. Otherwise, no amount of button-mashing fixes it.

Conversely, if every bucket count matches, then we can match each element of $S$ to some element of $T$ in the same bucket. Since numbers in the same bucket are mutually reachable, every matched element can be transformed correctly.

Therefore:

Convert every number $x$ into $\min(x \bmod k,\ k - (x \bmod k))$. Sort both arrays and compare.

Algorithm

For each test case:

1. Read $n$ and $k$.

2. For every element $x$ in $S$, compute:

   $c = \min(x \bmod k, k - (x \bmod k))$

3. Do the same for every element in $T$.

4. Sort both transformed arrays.

5. If they are equal, print YES; otherwise print NO.

Complexity

For each test case, sorting dominates:

$O(n \log n)$

The total $n$ over all test cases is at most $2 \cdot 10^5$, so this is easily fine.