CF2110C Racing

在 2077 年，一项名为"业余无人机竞速"的运动在机器人中越来越流行。 你已经拥有一架无人机，并且想要获胜。为此，你的无人机需要飞越一个包含 $n$ 个障碍物的赛道。 第 $i$ 个障碍物由两个数字 $l_i, r_i$ 定义。设你的无人机在第 $i$ 个障碍物处的高度为 $h_i$，那么当且仅当 $l_i \le h_i \le r_i$ 时，无人机才能通过该障碍物。初始时无人机位于地面，即 $h_0 = 0$。 无人机的飞行程序由一个数组 $d_1, d_2, \ldots, d_n$ 表示，其中 $h_{i} - h_{i-1} = d_i$，且 $0 \leq d_i \leq 1$。这意味着你的无人机在障碍物之间要么保持高度不变，要么上升 $1$ 个单位。你已经有一个飞行程序，但其中某些 $d_i$ 未知并被标记为 $-1$。你需要将这些未知的 $d_i$ 替换为 $0$ 或 $1$，以创建一个能完整通过所有障碍物的飞行程序，或者报告这是不可能的。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组 $d$ 的大小。 每个测试用例的第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$（$-1 \leq d_i \leq 1$）——数组 $d$ 的元素。$d_i = -1$ 表示该 $d_i$ 是未知的。 接下来 $n$ 行，每行包含 $2$ 个整数 $l_i, r_i$（$0 \leq l_i \leq r_i \leq n$）——障碍物的描述。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果能够正确恢复数组 $d$，则输出 $n$ 个整数 $d_1, d_2, \ldots, d_n$；如果不可能，则输出 $-1$。

在第一个测试用例中，一个可能的答案是 $d=[0,1,1,1]$。此时数组 $h$ 将为 $[0,0+1,0+1+1,0+1+1+1]=[0,1,2,3]$。这个数组满足题目条件。 在第二个测试用例中，可以证明不存在满足条件的数组 $d$，因此答案为 $-1$。 翻译由 DeepSeek V3 完成