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

У Кристины был массив $$$a$$$ длины $$$n$$$, состоящий из неотрицательных целых чисел.

Она построила новый массив $$$b$$$ длины $$$n-1$$$, такой что $$$b_i = \max(a_i, a_{i+1})$$$ ($$$1 \le i \le n-1$$$).

Например, пусть у Кристины был массив $$$a$$$ = [$$$3, 0, 4, 0, 5$$$] длины $$$5$$$. Тогда она сделала следующее:

  1. Посчитала $$$b_1 = \max(a_1, a_2) = \max(3, 0) = 3$$$;
  2. Посчитала $$$b_2 = \max(a_2, a_3) = \max(0, 4) = 4$$$;
  3. Посчитала $$$b_3 = \max(a_3, a_4) = \max(4, 0) = 4$$$;
  4. Посчитала $$$b_4 = \max(a_4, a_5) = \max(0, 5) = 5$$$.
В результате она получила массив $$$b$$$ = [$$$3, 4, 4, 5$$$] длины $$$4$$$.

Вам известен только массив $$$b$$$. Найдите любой подходящий массив $$$a$$$, который мог быть у Кристины изначально.

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

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

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных записано единственное целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$, который был у Кристины изначально.

Во второй строке каждого набора входных данных записано ровно $$$n-1$$$ целое неотрицательное число — элементы массива $$$b$$$ ($$$0 \le b_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$, и что массив $$$b$$$ был получен корректным образом из некоторого массива $$$a$$$.

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

Для каждого набора входных данных в отдельной строке выведите ровно $$$n$$$ целых неотрицательных чисел — элементы массива $$$a$$$, который был у Кристины изначально.

Если возможных ответов несколько — выведите любой из них.

Пример
Входные данные
11
5
3 4 4 5
4
2 2 1
5
0 0 0 0
6
0 3 4 4 3
2
10
4
3 3 3
5
4 2 5 5
4
3 3 3
4
2 1 0
3
4 4
6
8 1 3 5 10
Выходные данные
3 0 4 0 5
2 2 1 1
0 0 0 0 0
0 0 3 4 3 3
10 10
3 3 3 1
4 2 2 5 5
3 3 3 3
2 1 0 0
2 4 4
8 1 1 3 5 10
Примечание

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

Во втором наборе входных данных мы действительно можем получить из массива $$$a$$$ = [$$$2, 2, 1, 1$$$] массив $$$b$$$ = [$$$2, 2, 1$$$]:

  • $$$b_1 = \max(a_1, a_2) = \max(2, 2) = 2$$$;
  • $$$b_2 = \max(a_2, a_3) = \max(2, 1) = 2$$$;
  • $$$b_3 = \max(a_3, a_4) = \max(1, 1) = 1$$$.

В третьем наборе входных данных все элементы массива $$$b$$$ являются нулями. Так как каждый $$$b_i$$$ — максимум из двух соседних элементов массива $$$a$$$, то массив $$$a$$$ может состоять только целиком из нулей.

В четвертом наборе входных данных мы действительно можем получить из массива $$$a$$$ = [$$$0, 0, 3, 4, 3, 3$$$] массив $$$b$$$ = [$$$0, 3, 4, 4, 3$$$]:

  • $$$b_1 = \max(a_1, a_2) = \max(0, 0) = 0$$$;
  • $$$b_2 = \max(a_2, a_3) = \max(0, 3) = 3$$$;
  • $$$b_3 = \max(a_3, a_4) = \max(3, 4) = 4$$$;
  • $$$b_4 = \max(a_4, a_5) = \max(4, 3) = 4$$$;
  • $$$b_5 = \max(a_5, a_6) = \max(3, 3) = 3$$$.