Вам дан массив \(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\), удовлетворяющих условию, вы можете найти любой.
Выходные данные
Для каждого набора входных данных выведите любой массив \(a_1,\dots,a_n\) (\(1 \le a_i \le 10^9\)), удовлетворяющий условию.
Примечание
В первом наборе входных данных \(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\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|