У Алисии есть массив неотрицательных целых чисел \(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\) целых чисел, \(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\).
Гарантируется, что на всех данных тестах есть хотя бы одно решение. Можно показать, что в таком случае решение единственно.
Примечание
Первый тест разобран в условии задачи.
Во втором тесте, если у Алисии был массив \(a = \{1000, 1000000000, 0\}\), то \(x = \{0, 1000, 1000000000\}\) и \(b = \{1000-0, 1000000000-1000, 0-1000000000\} = \{1000, 999999000, -1000000000\}\).