Вам задан отсортированный массив \(a_1, a_2, \dots, a_n\). Вы решили получить из него массив \(b_1, b_2, \dots, b_n\) следующим образом:
- Создайте массив \(d\), состоящий из \(n\) произвольных неотрицательных целых чисел.
- Присвойте \(b_i = a_i + d_i\) для каждого \(b_i\).
- Отсортируйте массив \(b\) в порядке неубывания.
Вам задан полученный в результате массив \(b\). Посчитайте для каждого \(i\), какое минимально и максимально возможное значение \(d_i\) вы можете выбрать так, чтобы было возможно получить массив \(b\).
Заметим, что минимальные (максимальные) \(d_i\) считаются независимо друг от друга, т. е. могут быть получены из разных подходящих массивов \(d\).
Выходные данные
Для каждого набора входных данных выведите две строки. Во-первых, выведите \(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\).
Примечание
В первом наборе входных данных, для получения \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|