Restore the Weather solution codeforces
You are given an array 𝑎� containing the weather forecast for Berlandia for the last 𝑛� days. That is, 𝑎𝑖�� — is the estimated air temperature on day 𝑖� (1≤𝑖≤𝑛1≤�≤�).
You are also given an array 𝑏� — the air temperature that was actually present on each of the days. However, all the values in array 𝑏� are mixed up.
Determine which day was which temperature, if you know that the weather never differs from the forecast by more than 𝑘� degrees. In other words, if on day 𝑖� the real air temperature was 𝑐�, then the equality |𝑎𝑖−𝑐|≤𝑘|��−�|≤� is always true.
For example, let an array 𝑎� = [1,3,5,3,91,3,5,3,9] of length 𝑛=5�=5 and 𝑘=2�=2 be given and an array 𝑏� = [2,5,11,2,42,5,11,2,4]. Then, so that the value of 𝑏𝑖�� corresponds to the air temperature on day 𝑖�, we can rearrange the elements of the array 𝑏� so: [2,2,5,4,112,2,5,4,11]. Indeed:
- On the 11st day, |𝑎1−𝑏1|=|1−2|=1|�1−�1|=|1−2|=1, 1≤2=𝑘1≤2=� is satisfied;
- On the 22nd day |𝑎2−𝑏2|=|3−2|=1|�2−�2|=|3−2|=1, 1≤2=𝑘1≤2=� is satisfied;
- On the 33rd day, |𝑎3−𝑏3|=|5−5|=0|�3−�3|=|5−5|=0, 0≤2=𝑘0≤2=� is satisfied;
- On the 44th day, |𝑎4−𝑏4|=|3−4|=1|�4−�4|=|3−4|=1, 1≤2=𝑘1≤2=� is satisfied;
- On the 55th day, |𝑎5−𝑏5|=|9−11|=2|�5−�5|=|9−11|=2, 2≤2=𝑘2≤2=� is satisfied.
Restore the Weather solution codeforces
The first line of input data contains a single integer 𝑡� (1≤𝑡≤1041≤�≤104) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains two integers 𝑛� (1≤𝑛≤1051≤�≤105) and 𝑘� (0≤𝑘≤1090≤�≤109) — the number of days and the maximum difference between the expected and actual air temperature on each day.
The second line of each test case contains exactly 𝑛� integers — elements of array 𝑎� (−109≤𝑎𝑖≤109−109≤��≤109).
The third line of each test case contains exactly 𝑛� integers — elements of array 𝑏� (−109≤𝑏𝑖≤109−109≤��≤109).
It is guaranteed that the sum of 𝑛� over all test cases does not exceed 105105, and that the elements of array 𝑏� can always be rearranged so that the equality |𝑎𝑖−𝑏𝑖|≤𝑘|��−��|≤� is true for all 𝑖�.
On a separate line for each test case, output exactly 𝑛� numbers — the values of air temperature on each of the days in the correct order.
If there is more than one answer — output any of them.
2 2 5 4 11 0 4 -1 0 -4 0 8 4 9