Черепаха играла с последовательностью \(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\).
Выходные данные
Для каждого теста, если не существует последовательности \(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\). Если есть несколько ответов, выведите любой из них.
Примечание
В первом тесте, \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|