B. Максимумы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисии есть массив неотрицательных целых чисел $$$a_1, a_2, \ldots, a_n$$$. Для всех $$$1 \leq i \leq n$$$, она нашла число $$$x_i = max(0, a_1, \ldots, a_{i-1})$$$. Обратите внимание, что для $$$i=1$$$, $$$x_i = 0$$$.

Например, если у Алисии был массив $$$a = \{0, 1, 2, 0, 3\}$$$, то $$$x = \{0, 0, 1, 2, 2\}$$$.

Затем она вычислила значения массива $$$b_1, b_2, \ldots, b_n$$$: $$$b_i = a_i - x_i$$$.

Например, если у Алисии был массив $$$a = \{0, 1, 2, 0, 3\}$$$, то $$$b = \{0-0, 1-0, 2-1, 0-2, 3-2\} = \{0, 1, 1, -2, 1\}$$$.

Алисия дала вам массив $$$b_1, b_2, \ldots, b_n$$$ и попросила восстановить массив $$$a_1, a_2, \ldots, a_n$$$. Можете ли вы помочь ей с этой задачей?

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

В первой строке записано одно целое число $$$n$$$ ($$$3 \leq n \leq 200\,000$$$) — количество элементов в массиве Алисии.

Во второй строке записаны $$$n$$$ целых чисел, $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$).

Гарантируется, что для заданного массива $$$b$$$ существует решение $$$a_1, a_2, \ldots, a_n$$$, для всех элементов которого верно: $$$0 \leq a_i \leq 10^9$$$.

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

Выведите $$$n$$$ целых чисел, $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), таких, что если вы посчитаете $$$x$$$ согласно условию, $$$b_1$$$ будет равно $$$a_1 - x_1$$$, $$$b_2$$$ будет равно $$$a_2 - x_2$$$, ..., и $$$b_n$$$ будет равно $$$a_n - x_n$$$.

Гарантируется, что на всех данных тестах есть хотя бы одно решение. Можно показать, что в таком случае решение единственно.

Примеры
Входные данные
5
0 1 1 -2 1
Выходные данные
0 1 2 0 3
Входные данные
3
1000 999999000 -1000000000
Выходные данные
1000 1000000000 0
Входные данные
5
2 1 2 2 3
Выходные данные
2 3 5 7 10
Примечание

Первый тест разобран в условии задачи.

Во втором тесте, если у Алисии был массив $$$a = \{1000, 1000000000, 0\}$$$, то $$$x = \{0, 1000, 1000000000\}$$$ и $$$b = \{1000-0, 1000000000-1000, 0-1000000000\} = \{1000, 999999000, -1000000000\}$$$.