CF1981C.Turtle and an Incomplete Sequence

Turtle 正在玩一个由正整数组成的序列 $a_1, a_2, \ldots, a_n$。不幸的是，在玩耍过程中有一些整数丢失了。

现在这个序列变得不完整。可能存在任意多个下标 $i$，使得 $a_i$ 变成了 $-1$。记新的序列为 $a'$。

Turtle 很伤心。但 Turtle 记得，对于每一个从 $1$ 到 $n-1$ 的整数 $i$，原始序列 $a$ 满足 $a_i = \left\lfloor\frac{a_{i + 1}}{2}\right\rfloor$ 或 $a_{i + 1} = \left\lfloor\frac{a_i}{2}\right\rfloor$。

Turtle 想让你帮他补全这个序列。但有时候 Turtle 也会出错，所以如果你无法补全这个序列，需要告诉他。

形式化地说，你需要找到另一个由正整数组成的序列 $b_1, b_2, \ldots, b_n$，满足：

• 对于每一个 $1 \le i \le n$，如果 $a'_i \ne -1$，则 $b_i = a'_i$。
• 对于每一个 $1 \le i \le n-1$，要么 $b_i = \left\lfloor\frac{b_{i+1}}{2}\right\rfloor$，要么 $b_{i+1} = \left\lfloor\frac{b_i}{2}\right\rfloor$。
• 对于每一个 $1 \le i \le 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 i \le n$，$1 \le b_i \le 10^9$。如果有多组答案，输出任意一组均可。

在第一个测试用例中，$[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]$ 也是一个可行答案。

从第 4 到第 6 个测试用例，可以证明不存在可行解，因此你应该输出 $-1$。

由 ChatGPT 4.1 翻译