Nauuo是一个喜欢玩传送门相关游戏的女孩。
有一天,她正在玩一个游戏,如下所示。
在 $$$n\times n$$$ 网格中,行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$n$$$。我们将第 $$$r$$$ 行和第 $$$c$$$ 列的交叉点上的单元格表示为 $$$(r,c)$$$。
门户是一对门。您可以从其中一处前往另一处,而无需改变方向。更正式地说,如果您走进一个有门的牢房,您将传送到具有同一门户的另一扇门的牢房,然后走进面向原始方向的下一个牢房。一个牢房内不能有多于一扇门。
“下一个单元格”是您面向的方向最近的单元格。例如,如果您面朝底部,则 $$$(2,5)$$$ 的下一个单元格为 $$$(3,5)$$$。
如果你走进一个没有门的牢房,你必须在不改变方向的情况下走进下一个牢房。如果下一个单元格不存在,则必须退出网格。
你必须在网格中设置一些(可能为零)入口,这样如果你面朝右走进$$$(i,1)$$$,你最终将从$$$(r_i,n)$$$退出网格,如果面朝下走进$$$(1, i)$$$,你将从$$$(n,c_i)$$$退出网格。
保证 $$$r_{1..n}$$$ 和 $$$c_{1..n}$$$ 都是 $$$n$$$ 元素的排列。 $$$n$$$ 元素的排列是一个数字序列 $$$p_1,p_2,\ldots,p_n$$$,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。
她在玩游戏时感到困惑,你能帮她找到解决办法吗?
输入
第一行包含一个整数 $$$n$$$ ($$$1\le n\le 1000$$$) — 网格的边长。
第二行包含 $$$n$$$ 整数 $$$r_1,r_2,\ldots,r_n$$$ ($$$1\le r_i\le n$$$) — 如果你面向右走进 $$$(i,1)$$$,你应该从 $$$(r_i,n)$$$ 退出网格。保证 $$$r_{1..n}$$$ 是 $$$n$$$ 元素的排列。
第三行包含 $$$n$$$ 整数 $$$c_1,c_2,\ldots,c_n$$$ ($$$1\le c_i\le n$$$) — 如果你面朝底部走进 $$$(1,i)$$$,你应该从 $$$(n,c_i)$$$ 退出网格。保证 $$$c_{1..n}$$$ 是 $$$n$$$ 元素的排列。
输出
如果不可能满足规则,则打印唯一的数字$$$-1$$$。
否则,第一行应包含一个整数 $$$m$$$ ($$$0\le m\le\frac{n^2}2$$$) — 您设置的门户数量。
在接下来的$$$m$$$行中,每行应包含四个整数$$$x_1,y_1,x_2,y_2$$$,表示您在$$$(x_1,y_1)$$$和$$$(x_2,y_2)$$$中设置了一个由两扇门组成的传送门。
如果有多个答案,请打印其中一个。您不必最小化 $$$m$$$。
示例
输入 #1
3 1 3 2 3 1 2
输出 #1
2 1 1 1 3 2 2 3 1
输入 #2
5 3 1 5 4 2 4 2 1 3 5
输出 #2
3 1 1 3 4 2 2 3 2 2 3 5 1
注意
示例 1
具有相同字母的单元格是门户。您可以通过以下方式设置门户:
它满足规则,因为:
示例 2
您可以通过以下方式设置门户: