← 返回题目列表

Codeforces · 1833/B

B. 恢复天气

中文机器翻译题面 查看原题

给您一个数组 $$$a$$$,其中包含 Berlandia 最近 $$$n$$$ 天的天气预报。也就是说,$$$a_i$$$ — 是 $$$i$$$ 当天的估计气温 ($$$1 \le i \le n$$$)。

您还会获得一个数组 $$$b$$$ — 每一天实际存在的气温。但是,数组 $$$b$$$ 中的所有值都混合在一起。

如果您知道天气与预报的差异不会超过 $$$k$$$ 度,请确定哪一天的温度。换句话说,如果$$$i$$$当天的实际气温为$$$c$$$,则等式$$$|a_i - c| \le k$$$ 始终为真。

例如,给定一个长度为 $$$n = 5$$$ 且 $$$k = 2$$$ 的数组 $$$a$$$ = [$$$1, 3, 5, 3, 9$$$],并给出一个数组 $$$b$$$ = [$$$2, 5, 11, 2, 4$$$]。然后,为了使$$$b_i$$$的值对应于$$$i$$$当天的气温,我们可以重新排列数组$$$b$$$的元素,如下:[$$$2, 2, 5, 4, 11$$$]。确实:

- 在$$$1$$$第一天,$$$|a_1 - b_1| = |1 - 2| = 1$$$, $$$1 \le 2 = k$$$ 满足;
- 第 $$$2$$$ 天 $$$|a_2 - b_2| = |3 - 2| = 1$$$, $$$1 \le 2 = k$$$ 满足;
- 在第 $$$3$$$ 天,$$$|a_3 - b_3| = |5 - 5| = 0$$$, $$$0 \le 2 = k$$$ 满足;
- 在第 $$$4$$$ 天,$$$|a_4 - b_4| = |3 - 4| = 1$$$, $$$1 \le 2 = k$$$ 满足;
- 在第 $$$5$$$ 天,$$$|a_5 - b_5| = |9 - 11| = 2$$$, $$$2 \le 2 = k$$$ 满足。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) 和 $$$k$$$ ($$$0 \le k \le10^9$$$) - 天数以及每天的预期气温和实际气温之间的最大差异。

每个测试用例的第二行恰好包含 $$$n$$$ 个整数 — 数组 $$$a$$$ 的元素 ($$$-10^9 \le a_i \le 10^9$$$)。

每个测试用例的第三行恰好包含 $$$n$$$ 个整数 — 数组 $$$b$$$ 的元素 ($$$-10^9 \le b_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$,并且数组 $$$b$$$ 的元素始终可以重新排列,使得等式 $$$|a_i - b_i| \le k$$$ 对于所有 $$$i$$$ 都是正确的。

输出

在每个测试用例的单独一行中,准确输出 $$$n$$$ 数字 — 按正确顺序每天的气温值。

如果有多个答案 - 输出其中任何一个。

示例

输入 #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