给您一个数组 $$$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