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

Вам дан массив $$$x_2,x_3,\dots,x_n$$$. Ваша задача — найти любой массив $$$a_1,\dots,a_n$$$, для которого:

  • $$$1\le a_i\le 10^9$$$ для всех $$$1\le i\le n$$$.
  • $$$x_i=a_i \bmod a_{i-1}$$$ для всех $$$2\le i\le n$$$.

Здесь $$$c\bmod d$$$ обозначает остаток от целочисленного деления числа $$$c$$$ на число $$$d$$$. Например $$$5 \bmod 2 = 1$$$, $$$72 \bmod 3 = 0$$$, $$$143 \bmod 14 = 3$$$.

Обратите внимание, что если существует несколько массивов $$$a$$$, удовлетворяющих условию, вы можете найти любой.

Входные данные

Первая строка содержит одно целое число $$$t$$$ $$$(1\le t\le 10^4)$$$ — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ $$$(2\le n\le 500)$$$ — количество элементов в $$$a$$$.

Вторая строка каждого набора содержит $$$n-1$$$ целых чисел $$$x_2,\dots,x_n$$$ $$$(1\le x_i\le 500)$$$ — элементы $$$x$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите любой массив $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$), удовлетворяющий условию.

Пример
Входные данные
5
4
2 4 1
3
1 1
6
4 2 5 1 2
2
500
3
1 5
Выходные данные
3 5 4 9
2 5 11
5 14 16 5 11 24
501 500
2 7 5
Примечание

В первом наборе входных данных $$$a=[3,5,4,9]$$$ удовлетворяет условиям, потому что:

  • $$$a_2\bmod a_1=5\bmod 3=2=x_2$$$;
  • $$$a_3\bmod a_2=4\bmod 5=4=x_3$$$;
  • $$$a_4\bmod a_3=9\bmod 4=1=x_4$$$;