← 返回题目列表

Codeforces · 1172/D

D. Nauuo 和传送门

中文机器翻译题面 查看原题

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

您可以通过以下方式设置门户: