C. Min-Max Array Transformation
binary search; greedy; two pointers
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\): Create an array \(d\) consisting of \(n\) arbitrary non-negative integers. Set \(b_i = a_i + d_i\) for each \(b_i\). 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]\).