题目描述

有一个 $n\times n$ 的仓储网格，最开始每个格子都是空的。

你可以从网格边界的某个位置向内部推入一个货箱。若推入方向上的第一个格子已经有货箱，那么原来的货箱会继续沿该方向被往后顶，直到遇到空格为止。你不能把货箱推出网格之外。

现在你需要通过恰好 $n^2$ 次推入操作，把整个网格填满。

对于每个边界位置，定义四类操作：

• 从左边界第 $i$ 行推入，记作 $L_i$；
• 从右边界第 $i$ 行推入，记作 $R_i$；
• 从上边界第 $i$ 列推入，记作 $U_i$；
• 从下边界第 $i$ 列推入，记作 $D_i$。

例如，当 $n=3$ 时，边界位置可以表示为：

    U1  U2  U3
L1  __  __  __  R1
L2  __  __  __  R2
L3  __  __  __  R3
    D1  D2  D3

现在给定四个长度为 $n$ 的序列 $U,D,L,R$：

• $U_i$ 表示从上边界第 $i$ 列推入货箱的次数；
• $D_i$ 表示从下边界第 $i$ 列推入货箱的次数；
• $L_i$ 表示从左边界第 $i$ 行推入货箱的次数；
• $R_i$ 表示从右边界第 $i$ 行推入货箱的次数。

你需要构造一种填满整个网格的推入方案，使得每个边界位置被使用的次数恰好等于给定次数。

如果不存在合法方案，输出 -1。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数，依次表示：

$$U_1,U_2,\ldots,U_n$$

第三行 $n$ 个正整数，依次表示：

$$D_1,D_2,\ldots,D_n$$

第四行 $n$ 个正整数，依次表示：

$$L_1,L_2,\ldots,L_n$$

第五行 $n$ 个正整数，依次表示：

$$R_1,R_2,\ldots,R_n$$

输出格式

如果无解，输出 -1。

否则，输出 $n^2$ 行，每行两个正整数。

第一个正整数必须在 $[0,3]$ 内，表示本次操作从哪个边界推入：

• 0 表示从左边界推入，即 $L$；
• 1 表示从右边界推入，即 $R$；
• 2 表示从上边界推入，即 $U$；
• 3 表示从下边界推入，即 $D$。

第二个正整数必须在 $[1,n]$ 内，表示本次操作所在的行或列编号。

如果有多种合法方案，输出任意一种即可。

样例 1 输入

3
0 0 1
1 1 0
3 0 1
0 1 1

样例 1 输出

0 1
0 1
0 1
0 3
3 1
1 2
2 3
1 3
3 2

样例 1 解释

该输出给出了一种合法的填满 $3\times 3$ 网格的方案，并且每个边界位置的使用次数均满足输入要求。

样例 2 输入

3
3 0 0
3 0 0
3 0 0
0 0 0

样例 2 输出

-1

样例 3,4

见选手目录下：

• matrix/ex_matrix.3-4.in
• matrix/ex_matrix.3-4.out

分别满足子任务 3 和子任务 4 的限制。

测试点约束

对于所有数据，满足：

$$1\le n\le 300$$ $$0\le L_i,R_i,U_i,D_i\le n$$ $$\sum_{i=1}^{n}(L_i+R_i+U_i+D_i)=n^2$$

各子任务如下：

• 子任务 1：$n\le 3$，无特殊性质，分值 12。
• 子任务 2：$n\le 6$，无特殊性质，分值 12。
• 子任务 3：$n\le 300$，$U_i=0$ 且 $R_i=0$，分值 11。
• 子任务 4：$n\le 50$，无特殊性质，分值 30。
• 子任务 5：$n\le 300$，无特殊性质，分值 35。