P16966 [SCCPC 2026] 献给空白的无败冠冕

:::align{center}  ::: :::epigraph[游戏人生] 盟约既成，愿此局无败。 :::

在一切都由游戏决定的世界中，史蒂芬妮、空和白正在研究一个新的棋盘游戏。 棋盘是一个 $2\times n$ 的矩阵。第 $i$ 行第 $j$ 列的格子中有 $a_{i,j}$ 枚硬币。 游戏开始时，玩家站在格子 $(1,1)$，目标是移动到格子 $(2,n)$。每一步只能向右移动一格，或者向下移动一格。 由于棋盘只有两行，所以一条合法路径等价于选择一个下移列 $k$：先从 $(1,1)$ 走到 $(1,k)$，再向下走到 $(2,k)$，最后走到 $(2,n)$。 白先行动，并收集自己路径上的所有硬币。白结束后，空再行动，并收集自己路径上所有没有被白经过的格子中的硬币。白想让空所收集到的硬币数量最小化，而空想让自己收集到的硬币最大化。 史蒂芬妮认真观察了一会儿，然后自信地提出了一个策略：白只要选择自己能拿到最多硬币的路径，不就赢了吗？ 白沉默了一秒，指出这个策略并不一定正确。于是史蒂芬妮不服气地要求白立刻给出一个棋盘，使得她的策略会唯一地选择一条错误路径。可是白正在忙着和空博弈，于是把这个任务交给了你。 现在给你一个 $2\times n$ 的棋盘。棋盘中的一些位置已经给定为正整数，另一些位置为 $-1$。 你需要把所有 $-1$ 替换成 $[1,10^9]$ 内的正整数，使得构造后的棋盘满足以下条件： 存在唯一的路径，使得白拿到的硬币数量最大；并且史蒂芬妮的这个唯一选择是错误的，即存在另一种白的路径，使得空所能拿到的最大硬币数量更小。 如果无法构造这样的棋盘，输出 $-1$。

第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示棋盘的列数。 第二行包含 $n$ 个整数 $a_{1,1},a_{1,2},\ldots,a_{1,n}$，表示棋盘的第一行。 第三行包含 $n$ 个整数 $a_{2,1},a_{2,2},\ldots,a_{2,n}$，表示棋盘的第二行。 对于每个位置，均满足 $a_{i,j}=-1$，或者 $1\le a_{i,j}\le 10^9$。

如果无法构造，输出一行一个整数 $-1$。 否则输出两行，每行 $n$ 个整数，表示构造后的棋盘。