# [Solution] Min-Max Array Transformation solution codeforces

## Min-Max Array Transformation solution codeforces

Min-Max Array Transformation solution codeforces – You are given an array 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an, which is sorted in non-descending order. You decided to perform the following steps to create array 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn:

1. Create an array 𝑑d consisting of 𝑛n arbitrary non-negative integers.
2. Set 𝑏𝑖=𝑎𝑖+𝑑𝑖bi=ai+di for each 𝑏𝑖bi.
3. Sort the array 𝑏b in non-descending order.

## Min-Max Array Transformation solution codeforces

You are given the resulting array 𝑏b. For each index 𝑖i, calculate what is the minimum and maximum possible value of 𝑑𝑖di you can choose in order to get the given array 𝑏b.

Note that the minimum (maximum) 𝑑𝑖di-s are independent of each other, i. e. they can be obtained from different possible arrays 𝑑d.

Input

The first line contains the single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛21051≤n≤2⋅105) — the length of arrays 𝑎a𝑏b and 𝑑d.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109𝑎𝑖𝑎𝑖+1ai≤ai+1) — the array 𝑎a in non-descending order.

The third line contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖1091≤bi≤109𝑏𝑖𝑏𝑖+1bi≤bi+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 21052⋅105.

## Min-Max Array Transformation solution codeforces

For each test case, print two lines. In the first line, print 𝑛n integers 𝑑𝑚𝑖𝑛1,𝑑𝑚𝑖𝑛2,,𝑑𝑚𝑖𝑛𝑛d1min,d2min,…,dnmin, where 𝑑𝑚𝑖𝑛𝑖dimin is the minimum possible value you can add to 𝑎𝑖ai.

Secondly, print 𝑛n integers 𝑑𝑚𝑎𝑥1,𝑑𝑚𝑎𝑥2,,𝑑𝑚𝑎𝑥𝑛d1max,d2max,…,dnmax, where 𝑑𝑚𝑎𝑥𝑖dimax is the maximum possible value you can add to 𝑎𝑖ai.

All 𝑑𝑚𝑖𝑛𝑖dimin and 𝑑𝑚𝑎𝑥𝑖dimax values are independent of each other. In other words, for each 𝑖i𝑑𝑚𝑖𝑛𝑖dimin is just the minimum value among all possible values of 𝑑𝑖di.

Example
input

Copy
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
output

Copy
5 4 2
11 10 8
4000
4000
0 0 0 0
0 0 0 0
12 2 3 15
23 13 3 15


## Min-Max Array Transformation solution codeforces

In the first test case, in order to get 𝑑𝑚𝑖𝑛1=5d1min=5, we can choose, for example, 𝑑=[5,10,6]d=[5,10,6]. Then 𝑏b == [2+5,3+10,5+6][2+5,3+10,5+6] == [7,13,11][7,13,11] == [7,11,13][7,11,13].

For 𝑑𝑚𝑖𝑛2=4d2min=4, we can choose 𝑑d == [9,4,8][9,4,8]. Then 𝑏b == [2+9,3+4,5+8][2+9,3+4,5+8] == [11,7,13][11,7,13] == [7,11,13][7,11,13].