CF1721C Min-Max Array Transformation

You are given an array $ a_1, a_2, \dots, a_n $ , which is sorted in non-descending order. You decided to perform the following steps to create array $ b_1, b_2, \dots, b_n $ : 1. Create an array $ d $ consisting of $ n $ arbitrary non-negative integers. 2. Set $ b_i = a_i + d_i $ for each $ b_i $ . 3. Sort the array $ b $ in non-descending order. You are given the resulting array $ b $ . For each index $ i $ , calculate what is the minimum and maximum possible value of $ d_i $ you can choose in order to get the given array $ b $ . Note that the minimum (maximum) $ d_i $ -s are independent of each other, i. e. they can be obtained from different possible arrays $ d $ .

The first line contains the single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of arrays $ a $ , $ b $ and $ d $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ; $ a_i \le a_{i+1} $ ) — the array $ a $ in non-descending order. The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le 10^9 $ ; $ b_i \le b_{i+1} $ ) — the array $ b $ in non-descending order. Additional constraints on the input: - there is at least one way to obtain the array $ b $ from the $ a $ by choosing an array $ d $ consisting of non-negative integers; - the sum of $ n $ doesn't exceed $ 2 \cdot 10^5 $ .

For each test case, print two lines. In the first line, print $ n $ integers $ d_1^{min}, d_2^{min}, \dots, d_n^{min} $ , where $ d_i^{min} $ is the minimum possible value you can add to $ a_i $ . Secondly, print $ n $ integers $ d_1^{max}, d_2^{max}, \dots, d_n^{max} $ , where $ d_i^{max} $ is the maximum possible value you can add to $ a_i $ . All $ d_i^{min} $ and $ d_i^{max} $ values are independent of each other. In other words, for each $ i $ , $ d_i^{min} $ is just the minimum value among all possible values of $ d_i $ .

In the first test case, in order to get $ d_1^{min} = 5 $ , we can choose, for example, $ d = [5, 10, 6] $ . Then $ b $ $ = $ $ [2+5,3+10,5+6] $ $ = $ $ [7,13,11] $ $ = $ $ [7,11,13] $ . For $ d_2^{min} = 4 $ , we can choose $ d $ $ = $ $ [9, 4, 8] $ . Then $ b $ $ = $ $ [2+9,3+4,5+8] $ $ = $ $ [11,7,13] $ $ = $ $ [7,11,13] $ .