CF1833B.Restore the Weather
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a containing the weather forecast for Berlandia for the last n days. That is, ai — is the estimated air temperature on day i ( 1≤i≤n ).
You are also given an array b — the air temperature that was actually present on each of the days. However, all the values in array b are mixed up.
Determine which day was which temperature, if you know that the weather never differs from the forecast by more than k degrees. In other words, if on day i the real air temperature was c , then the equality ∣ai−c∣≤k is always true.
For example, let an array a = [ 1,3,5,3,9 ] of length n=5 and k=2 be given and an array b = [ 2,5,11,2,4 ]. Then, so that the value of bi corresponds to the air temperature on day i , we can rearrange the elements of the array b so: [ 2,2,5,4,11 ]. Indeed:
- On the 1 st day, ∣a1−b1∣=∣1−2∣=1 , 1≤2=k is satisfied;
- On the 2 nd day ∣a2−b2∣=∣3−2∣=1 , 1≤2=k is satisfied;
- On the 3 rd day, ∣a3−b3∣=∣5−5∣=0 , 0≤2=k is satisfied;
- On the 4 th day, ∣a4−b4∣=∣3−4∣=1 , 1≤2=k is satisfied;
- On the 5 th day, ∣a5−b5∣=∣9−11∣=2 , 2≤2=k is satisfied.
输入格式
The first line of input data contains a single integer t ( 1≤t≤104 ) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains two integers n ( 1≤n≤105 ) and k ( 0≤k≤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 n integers — elements of array a ( −109≤ai≤109 ).
The third line of each test case contains exactly n integers — elements of array b ( −109≤bi≤109 ).
It is guaranteed that the sum of n over all test cases does not exceed 105 , and that the elements of array b can always be rearranged so that the equality ∣ai−bi∣≤k is true for all i .
输出格式
On a separate line for each test case, output exactly n 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.
输入输出样例
输入#1
3 5 2 1 3 5 3 9 2 5 11 2 4 6 1 -1 3 -2 0 -5 -1 -4 0 -1 4 0 0 3 3 7 7 7 9 4 8
输出#1
2 2 5 4 11 0 4 -1 0 -4 0 8 4 9