给定一个数组 $$$a_1, a_2, \dots, a_n$$$,该数组按非降序排序。您决定执行以下步骤来创建数组 $$$b_1, b_2, \dots, b_n$$$:
1. 创建一个由 $$$n$$$ 任意非负整数组成的数组 $$$d$$$。
2. 对每个 $$$b_i$$$ 设置 $$$b_i = a_i + d_i$$$。
3. 按非降序对数组 $$$b$$$ 进行排序。
您将得到结果数组$$$b$$$。对于每个索引 $$$i$$$,计算您可以选择的 $$$d_i$$$ 的最小和最大可能值,以获得给定的数组 $$$b$$$。
请注意,最小(最大)$$$d_i$$$-s 彼此独立,i。 e.它们可以从不同的可能数组 $$$d$$$ 中获得。
输入
第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$、$$$b$$$ 和 $$$d$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$; $$$a_i \le a_{i+1}$$$) - 数组 $$$a$$$ 按非降序排列。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$; $$$b_i \le b_{i+1}$$$) - 数组 $$$b$$$ 按非降序排列。
输入的附加限制:
- 至少有一种方法可以通过选择由非负整数组成的数组$$$d$$$来从$$$a$$$获取数组$$$b$$$;
- $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印两行。在第一行中,打印 $$$n$$$ 整数 $$$d_1^{min}, d_2^{min}, \dots, d_n^{min}$$$,其中 $$$d_i^{min}$$$ 是可以添加到 $$$a_i$$$ 的最小可能值。
其次,打印 $$$n$$$ 整数 $$$d_1^{max}, d_2^{max}, \dots, d_n^{max}$$$,其中 $$$d_i^{max}$$$ 是可以添加到 $$$a_i$$$ 的最大可能值。
所有 $$$d_i^{min}$$$ 和 $$$d_i^{max}$$$ 值彼此独立。换句话说,对于每个$$$i$$$,$$$d_i^{min}$$$只是$$$d_i$$$所有可能值中的最小值。
示例
输入 #1
4 3 2 3 5 7 11 13 1 1000 5000 4 1 2 3 4 1 2 3 4 4 10 20 30 40 22 33 33 55
输出 #1
5 4 2 11 10 8 4000 4000 0 0 0 0 0 0 0 0 12 2 3 15 23 13 3 15
注意
在第一个测试用例中,为了得到$$$d_1^{min} = 5$$$,我们可以选择例如$$$d = [5, 10, 6]$$$。然后$$$b$$$$$$=$$$$$$[2+5,3+10,5+6]$$$$$$=$$$$$$[7,13,11]$$$$$$=$$$$$$[7,11,13]$$$。
对于 $$$d_2^{min} = 4$$$,我们可以选择 $$$d$$$ $$$=$$$ $$$[9, 4, 8]$$$。然后$$$b$$$$$$=$$$$$$[2+9,3+4,5+8]$$$$$$=$$$$$$[11,7,13]$$$$$$=$$$$$$[7,11,13]$$$。