C. Мин-макс преобразование массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан отсортированный массив $$$a_1, a_2, \dots, a_n$$$. Вы решили получить из него массив $$$b_1, b_2, \dots, b_n$$$ следующим образом:

  1. Создайте массив $$$d$$$, состоящий из $$$n$$$ произвольных неотрицательных целых чисел.
  2. Присвойте $$$b_i = a_i + d_i$$$ для каждого $$$b_i$$$.
  3. Отсортируйте массив $$$b$$$ в порядке неубывания.

Вам задан полученный в результате массив $$$b$$$. Посчитайте для каждого $$$i$$$, какое минимально и максимально возможное значение $$$d_i$$$ вы можете выбрать так, чтобы было возможно получить массив $$$b$$$.

Заметим, что минимальные (максимальные) $$$d_i$$$ считаются независимо друг от друга, т. е. могут быть получены из разных подходящих массивов $$$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$$$, состоящий из неотрицательных целых чисел, чтобы получить массив $$$b$$$ из $$$a$$$;
  • сумма $$$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$$$.

Пример
Входные данные
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
Выходные данные
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]$$$.