在一切都由游戏决定的世界中,史蒂芬妮、空和白正在研究一个新的棋盘游戏。
棋盘是一个 $$$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$$$ 个整数,表示构造后的棋盘。
3 5 -1 2 -1 2 7
5 1 2 2 2 7
1-11
-1