Вам дан массив \([a_1, a_2, \dots, a_n]\) такой, что \(1 \le a_i \le 10^9\). Пусть \(S\) – сумма всех элементов массива \(a\).
Назовем массив \(b\), состоящий из \(n\) целых чисел красивым, если:
- \(1 \le b_i \le 10^9\) для всех \(i\) от \(1\) до \(n\);
- для каждой пары соседних целых чисел из массива \((b_i, b_{i + 1})\), либо \(b_i\) делит \(b_{i + 1}\), либо \(b_{i + 1}\) делит \(b_i\) (или оба числа делятся друг на друга);
- \(2 \sum \limits_{i = 1}^{n} |a_i - b_i| \le S\).
Ваша задача — найти красивый массив. Можно показать, что по крайней мере один красивый массив всегда существует.
Выходные данные
Для каждого набора входных данных выведите красивый массив \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le 10^9\)) на отдельной строке. Можно показать, что существует по крайней мере один красивый массив. Если ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
1 2 3 4 5
2
4 6
2
1 1000000000
6
3 4 8 1 2 3
|
3 3 3 3 3
3 6
1 1000000000
4 4 8 1 3 3
|