310435: CF1833B. Restore the Weather
Description
You are given an array $a$ containing the weather forecast for Berlandia for the last $n$ days. That is, $a_i$ — is the estimated air temperature on day $i$ ($1 \le i \le 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 $|a_i - c| \le 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 $b_i$ 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, $|a_1 - b_1| = |1 - 2| = 1$, $1 \le 2 = k$ is satisfied;
- On the $2$nd day $|a_2 - b_2| = |3 - 2| = 1$, $1 \le 2 = k$ is satisfied;
- On the $3$rd day, $|a_3 - b_3| = |5 - 5| = 0$, $0 \le 2 = k$ is satisfied;
- On the $4$th day, $|a_4 - b_4| = |3 - 4| = 1$, $1 \le 2 = k$ is satisfied;
- On the $5$th day, $|a_5 - b_5| = |9 - 11| = 2$, $2 \le 2 = k$ is satisfied.
The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains two integers $n$ ($1 \le n \le 10^5$) and $k$ ($0 \le k \le10^9$) — 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$ ($-10^9 \le a_i \le 10^9$).
The third line of each test case contains exactly $n$ integers — elements of array $b$ ($-10^9 \le b_i \le 10^9$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and that the elements of array $b$ can always be rearranged so that the equality $|a_i - b_i| \le k$ is true for all $i$.
OutputOn 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.
ExampleInput3 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 8Output
2 2 5 4 11 0 4 -1 0 -4 0 8 4 9
Input
题意翻译
本题有 $t$ 组测试数据。 对于每组测试数据，给定整数 $n$,$k$ 与两个长度为 $n$ 的数组 $a$ 与 $b$。 要求重新排列 $b$ 使得对于每一个 $1\le i \le n$，满足 $|a_i - b_i| \le k$ 保证一定有解。 对于 $100\%$ 的数据满足： * $1 \le t \le 10^4$ * $\sum_{i=1}^t n \le 10^5$ * $-10^9 \le a_i, b_i \le 10^9$ * $0 \le k \le 10^9$Output
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含两个整数n（1≤n≤10^5）和k（0≤k≤10^9）——天数和每天预测与实际气温之间的最大差异。
- 第二行包含n个整数——数组a的元素（-10^9≤a[i]≤10^9）。
- 第三行包含n个整数——数组b的元素（-10^9≤b[i]≤10^9）。
- 保证所有测试用例的n之和不超过10^5，且数组b的元素可以重新排列以满足对所有i，|a[i] - b[i]| ≤ k的条件。
输出：
- 对于每个测试用例，输出一行恰好n个数字——每天的正确气温值。
- 如果有多个答案，输出其中任意一个。题目大意：给定一个数组a，包含贝尔兰迪亚过去n天的天气预报，即a[i]是第i天的预测气温（1≤i≤n）。还给定一个数组b，包含实际每天的气温，但数组b的值是混乱的。如果知道天气与预报的差异不会超过k度，则确定哪一天对应哪个气温。换句话说，如果第i天的实际气温是c，则|a[i] - c| ≤ k始终成立。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含两个整数n（1≤n≤10^5）和k（0≤k≤10^9）——天数和每天预测与实际气温之间的最大差异。 - 第二行包含n个整数——数组a的元素（-10^9≤a[i]≤10^9）。 - 第三行包含n个整数——数组b的元素（-10^9≤b[i]≤10^9）。 - 保证所有测试用例的n之和不超过10^5，且数组b的元素可以重新排列以满足对所有i，|a[i] - b[i]| ≤ k的条件。 输出： - 对于每个测试用例，输出一行恰好n个数字——每天的正确气温值。 - 如果有多个答案，输出其中任意一个。