В длинном коридоре установлены n неоновых панелей, пронумерованных от 1 до n.

Каждая панель кодируется неотрицательным целым числом: если некоторый бит равен 1, то соответствующий цвет в этой панели включён, а если 0 — выключен.

Инженеры проверяли только соседние пары панелей. Для каждой пары соседей они записали число b_i, равное побитовому AND кодов этих панелей:

b_i = a_i & a_{i+1}

где:

• a_i — код i-й панели,
• & — операция побитового AND.

По массиву b восстановите любой массив a, который мог породить такие результаты проверок.

Если подходящего массива a не существует, выведите -1.

Формат входных данных

В первой строке записано целое число t — количество наборов данных.

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

Для каждого набора данных:

• в первой строке записано целое число n — количество панелей;
• во второй строке записаны n-1 целых чисел b_1, b_2, ..., b_{n-1}.

Формат выходных данных

Для каждого набора данных:

• выведите -1, если подходящего массива не существует;
• иначе выведите n неотрицательных целых чисел a_1, a_2, ..., a_n.

Если решений несколько, разрешается вывести любое.

Ограничения

• 1 <= t <= 10^4
• 2 <= n <= 10^5
• 0 <= b_i < 2^30
• сумма всех n по всем наборам данных не превосходит 10^5

Примеры

Пример 1

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

3
4
1 3 1
2
0
5
2 4 4 2

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

1 3 3 1
0 0
2 6 4 6 2

Примечание

Побитовое AND двух чисел сравнивает их двоичные записи поразрядно:

• если в обоих числах бит равен 1, то в результате он тоже равен 1;
• иначе результат в этом бите равен 0.