题目描述

一个 $N\times N$ 的 $0/1$ 矩阵称为“Calafat 矩阵”，当且仅当它满足：

• 每一行恰好有两个 $1$；
• 每一列恰好有两个 $1$；
• 其它位置均为 $0$。

现在给定两个这样的矩阵 $A$ 和 $B$。你需要通过交换矩阵 $B$ 的若干行和若干列，将 $B$ 变成 $A$。

题目保证所有输入数据均有解。

输入格式

第一行包含整数 $N$，表示矩阵大小。

接下来 $2N$ 行，每行两个整数 $x,y$，表示矩阵 $A$ 中一个值为 $1$ 的元素位置为第 $x$ 行第 $y$ 列。

再接下来 $2N$ 行，每行两个整数 $x,y$，表示矩阵 $B$ 中一个值为 $1$ 的元素位置为第 $x$ 行第 $y$ 列。

输出格式

每行输出一个操作，格式为：

ch x y

其中 ch 只能为 L、C 或 0：

• 若 ch = L，表示交换矩阵 $B$ 的第 $x$ 行和第 $y$ 行；
• 若 ch = C，表示交换矩阵 $B$ 的第 $x$ 列和第 $y$ 列；
• 最后一行必须输出：

0 0 0

表示操作结束。

数据范围与评分

• $1\le N\le 80000$；
• 题目保证存在解。

设实际执行的交换操作数为 $op$，不计最后的 0 0 0。若输出正确，则按如下规则给分：

• $1\le op\le 2N$：获得 $100\%$ 分数；
• $2N+1\le op\le 4N$：获得 $75\%$ 分数；
• $op>4N$：获得 $50\%$ 分数。

样例

输入

4
1 1
2 2
3 3
4 1
3 4
4 4
2 3
1 2
1 3
2 3
1 1
2 2
4 2
4 4
3 4
3 1

输出

L 3 4
C 3 2
0 0 0

样例解释

先读入矩阵 $A$：

1 1 0 0
0 1 1 0
0 0 1 1
1 0 0 1

再读入矩阵 $B$：

1 0 1 0
0 1 1 0
1 0 0 1
0 1 0 1

交换第 $3$ 行与第 $4$ 行后，再交换第 $3$ 列与第 $2$ 列，即可得到矩阵 $A$。