3.5 Magical Potion Equalizer
In the kingdom of Numeria, a wizard has two collections of magical stones, S and T, each containing n stones. Each stone has a power level, represented by a non-negative integer.
The wizard also possesses a magical wand with power k. Using the wand, the wizard can perform the following spell any number of times on the stones in S:
Pick any stone with power x from S, remove it, and either:
-Increase its power by k and place its absolute value back, or
-Decrease its power by k and place its absolute value back.
The wizard wants to know if it’s possible to transform the collection S so that it exactly matches the collection T, including the number of stones of each power level.
Help the wizard determine if this magical transformation is possible.
Constraints
1 ≤ t ≤ 10⁴
1 ≤ n ≤ 2⋅10⁵, 1 ≤ k ≤ 10⁹
0 ≤ Sᵢ ≤ 10⁹
0 ≤ Tᵢ ≤ 10⁹
Input Format
The first line contains a single integer t — the number of scenarios the wizard wants to try.
Each scenario starts with a line containing two integers n and k — the number of stones and the wand’s power.
The next line contains n integers S₁, S₂, …, Sₙ — the power levels of the stones in S.
The next line contains n integers T₁, T₂, …, Tₙ — the power levels of the stones in T.
Output Format
For each scenario, output "YES" if the wizard can transform S to match T, or "NO" otherwise.
Example 1
Input:
2
3 2
1 3 5
3 5 7
4 3
2 4 6 8
1 7 5 10
Output:
YES
NO
Explanation:
Test case 1:
n = 3, k = 2
S = [1, 3, 5], T = [3, 5, 7]
Transformation:
1 → 3 (1 + 2), 3 → 5 (3 + 2), 5 → 7 (5 + 2)
S matches T
Test case 2:
Trying any combination of +3 or |x−3| on S cannot produce 1, 5, 7, 10 exactly.
Therefore, achieving T is impossible
Log In to solve the Question