C. Черепаха и неполная последовательность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Черепаха играла с последовательностью $$$a_1, a_2, \ldots, a_n$$$, состоящей из положительных целых чисел. К сожалению, некоторые числа пропали во время игры.

Теперь последовательность стала неполной. Может существовать произвольное количество индексов $$$i$$$, таких что $$$a_i$$$ становится $$$-1$$$. Пусть новая последовательность будет $$$a'$$$.

Черепаха грустит. Но Черепаха помнит, что для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n - 1$$$, либо $$$a_i = \left\lfloor\frac{a_{i + 1}}{2}\right\rfloor$$$, либо $$$a_{i + 1} = \left\lfloor\frac{a_i}{2}\right\rfloor$$$ выполняется для исходной последовательности $$$a$$$.

Черепаха хочет, чтобы вы помогли ей завершить последовательность. Но иногда Черепаха ошибается, поэтому вам нужно сказать ей, если вы не можете завершить последовательность.

Формально, вам нужно найти другую последовательность $$$b_1, b_2, \ldots, b_n$$$, состоящую из положительных целых чисел, такую что:

  • Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n$$$, если $$$a'_i \ne -1$$$, то $$$b_i = a'_i$$$.
  • Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n - 1$$$, либо $$$b_i = \left\lfloor\frac{b_{i + 1}}{2}\right\rfloor$$$, либо $$$b_{i + 1} = \left\lfloor\frac{b_i}{2}\right\rfloor$$$ выполняется.
  • Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n$$$, $$$1 \le b_i \le 10^9$$$.

Если не существует последовательности $$$b_1, b_2, \ldots, b_n$$$, которая удовлетворяет всем условиям выше, вам нужно сообщить $$$-1$$$.

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

Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестов $$$t$$$ ($$$1 \le t \le 10^5$$$). Затем следует описание тестов.

Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина последовательности.

Вторая строка каждого теста содержит $$$n$$$ целых чисел $$$a'_1, a'_2, \ldots, a'_n$$$ ($$$a'_i = -1$$$ или $$$1 \le a'_i \le 10^8$$$) — элементы последовательности $$$a'$$$.

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

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

Для каждого теста, если не существует последовательности $$$b_1, b_2, \ldots, b_n$$$, которая удовлетворяет всем условиям, выведите одно целое число $$$-1$$$.

В противном случае выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ — элементы последовательности $$$b_1, b_2, \ldots, b_n$$$, которую вы нашли. Последовательность должна удовлетворять условию $$$1 \le b_i \le 10^9$$$ для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n$$$. Если есть несколько ответов, выведите любой из них.

Пример
Входные данные
9
8
-1 -1 -1 2 -1 -1 1 -1
4
-1 -1 -1 -1
6
3 -1 -1 -1 9 -1
4
-1 5 -1 6
4
2 -1 -1 3
4
1 2 3 4
2
4 2
5
-1 3 -1 3 6
13
-1 -1 3 -1 -1 -1 -1 7 -1 -1 3 -1 -1
Выходные данные
4 9 4 2 4 2 1 2
7 3 6 13
3 1 2 4 9 18
-1
-1
-1
4 2
6 3 1 3 6
3 1 3 1 3 7 3 7 3 1 3 1 3
Примечание

В первом тесте, $$$[4, 2, 1, 2, 1, 2, 1, 3]$$$ также может быть ответом, в то время как $$$[4, 2, 5, 10, 5, 2, 1, 3]$$$ и $$$[4, 2, 1, 2, 1, 2, 1, 4]$$$ не могут.

Во втором тесте, $$$[1, 2, 5, 2]$$$ также может быть ответом.

С четвертого по шестой тесты, можно показать, что ответа нет, поэтому вы должны вывести $$$-1$$$.