题目描述Description

现有一个 2 行 n 列的网格，行从上到下编号为 1 到 2，列从左到右编号为 1 到 n。有 2n 种颜色，编号为 1 到 2n。目前一些格子已经被染色了，你需要对剩余格子进行染色（已经被染色的格子不能被重新染色），使得最后相同颜色组成的四连通块数量最少。请构造一种染色方案。

四连通是指，如果两个颜色相同的格子有一条公共边，那么我们认为这两个格子是连通的。

输入格式Input

第一行一个整数 n（1\le n\le 10^5）。

第二行 n 个整数 a_{1,1},a_{1,2},\ldots,a_{1,n}（0\le a_{1,i}\le 2n），表示网格第一行的染色情况。

第三行 n 个整数 a_{2,1},a_{2,2},\ldots,a_{2,n}（0\le a_{2,i}\le 2n），表示网格第二行的染色情况。

如果 a_{i,j}=0，则表示第 i 行第 j 列的单元格没有被染色，否则表示第 i 行第 j 列单元格的颜色为 a_{i,j}。保证最初至少有一个单元格满足 a_{i,j}\neq 0。

输出格式Output

输出两行，每行 n 个正整数 b_{i,j}（1\le b_{i,j}\le 2n），表示一种染色方案。输出需保证已经被染色的格子不能被重新染色，即，对于 a_{i,j}\neq 0 的单元格，输出应保证 b_{i,j}=a_{i,j}。

如有多种满足条件的染色方案，输出任意一种均可。

样例Sample

提示Hint

-

出题Author

来源Source