Вам задан отсортированный массив $$$a_1, a_2, \dots, a_n$$$. Вы решили получить из него массив $$$b_1, b_2, \dots, b_n$$$ следующим образом:
Вам задан полученный в результате массив $$$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$$$ в порядке неубывания.
Дополнительные ограничения на входные данные:
Для каждого набора входных данных выведите две строки. Во-первых, выведите $$$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$$$.
432 3 57 11 1311000500041 2 3 41 2 3 4410 20 30 4022 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]$$$.
