Min-Max Array Transformation
Contest: Educational Codeforces Round 134 (Rated for Div. 2)
Difficulty rating: 1400
Tags: 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$$$:

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$$$.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
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

Example output:
5 4 2
11 10 8
4000
4000
0 0 0 0
0 0 0 0
12 2 3 15
23 13 3 15

Editorial:
For the start, let's note that $$$a_i \le b_i$$$ for each $$$i$$$. Otherwise, there is no way to get $$$b$$$ from $$$a$$$.
Firstly, let's calculate $$$d_i^{min}$$$ for each $$$i$$$. Since all $$$d_i \ge 0$$$ then $$$b_j$$$ is always greater or equal than $$$a_i$$$ you get it from. So, the minimum $$$d_i$$$ would come from lowest $$$b_j$$$ that still $$$\ge a_i$$$. Since $$$b$$$ is sorted, we can find such $$$b_j$$$ with lower_bound in $$$O(\log{n})$$$.
Let's prove that we can build such $$$d$$$ that transforms $$$a_i$$$ to $$$b_j$$$ we found earlier. Let's just make $$$d_k = b_k - a_k$$$ for $$$k \in [1..j) \cup (i..n]$$$; $$$d_k = b_{k+1} - a_k$$$ for $$$k \in [j..i)$$$ and $$$d_i = b_j - a_i$$$. It's easy to see that all $$$d_i$$$ are non-negative, so such $$$d$$$ is valid.
Now, let's calculate $$$d_i^{max}$$$. Suppose, we transform $$$a_i$$$ to $$$b_j$$$ for some $$$j \ge i$$$. It's not hard to prove that the "proving" array $$$d$$$ may be constructed in the similar way: $$$d_k = b_k - a_k$$$ for $$$k \in [1..i) \cup (j..n]$$$; $$$d_k = b_{k-1} - a_k$$$ for $$$k \in (i..j]$$$ and $$$d_i = b_j - a_i$$$.
In order to build such array $$$d$$$, you need $$$b_{k-1} \ge a_k$$$ for each $$$i \in (i..j]$$$. In other words, if there is some position $$$l$$$ such that $$$l > i$$$ and $$$b_{l - 1} < a_l$$$ you can't choose $$$j$$$ such that $$$j \ge l$$$. It means that we can iterate $$$i$$$ in descending order and just keep track of leftmost $$$l \ge i$$$ with $$$b_{l - 1} < a_l$$$. Then, $$$d_i^{max}$$$ is equal to $$$b[l - 1] - a[i]$$$ (or $$$b[n] - a[i]$$$ if there are no such $$$l$$$).
The resulting complexity is $$$O(n \log n)$$$ because of the first part. But it can be optimized to $$$O(n)$$$ if we use two pointers instead of lower_bound.