题目背景

在距今 $1890$ 万年之后，XYH 和 AEY 生活在 648 号小宇宙中。这个小宇宙属于他们二人，是他们在大宇宙垂暮之时共同见证的甜蜜、美好的世界。

突然，648 号小宇宙遭遇了一次宇宙射线风暴，小宇宙变得七零八落。眼看一切美好即将崩颓，XYH 和 AEY 向大宇宙发出了求救信号。

题目描述

小宇宙的结构可以用一个“宇宙魔方”表示。只要还原宇宙魔方，小宇宙就会被拯救。

宇宙魔方是一个正四面体。它的每条棱上均匀分布着 $n$ 颗小球，其中 $n\le 1000$。这些小球共有 $6$ 种颜色，并且每种颜色恰好有 $n$ 颗。

若每条棱上的所有小球颜色均相同，则称宇宙魔方处于还原状态。

你可以执行以下两类操作。

第一类操作

选择一个顶点，再选择一个整数 $d\in[1,n]$。

对于与该顶点相邻的每一条棱，选中距离该顶点第 $d$ 近的小球。这样一共会选中 $3$ 颗小球。你可以将这 $3$ 颗小球所组成的三角形顺时针或逆时针旋转，即循环替换它们的位置。

第二类操作

选择一条棱，再选择一个整数

$$d\in\left[1,\left\lfloor\frac n2\right\rfloor\right].$$

将该棱上从两端向内数、互相对称的第 $d$ 对小球交换位置。

为了描述顶点间的相对位置，将四个顶点命名为 $A,B,C,D$。把由 $A,B,C$ 构成的面平放在桌面上，并规定从上方观察时，$A,B,C$ 三个顶点按顺时针顺序排列。

左侧为一个处于还原状态、$n=2$ 的宇宙魔方俯视图；依次执行一次第一类操作和一次第二类操作后，得到右下角状态。当前压缩包未包含该图片。

现在给定一个宇宙魔方的初始状态。保证该状态可以由某个还原状态经过若干次合法操作得到。

请在不超过 $m$ 次操作内将它还原，其中 $m\ge 2.5\times 10^4$。

输入格式

第一行输入两个正整数 $n,m$。

接下来 $6$ 行，每行输入 $n$ 个 $1\sim 6$ 的整数，依次表示以下方向上排列的小球颜色：

1. $A\to B$；
2. $A\to C$；
3. $A\to D$；
4. $B\to C$；
5. $B\to D$；
6. $C\to D$。

输出格式

第一行输出一个整数 $k$，表示你构造的操作序列长度，要求 $k\le m$。

接下来输出 $k$ 行，每行描述一次操作。

第一类操作格式

1 V d dir

其中：

• V 是顶点 A、B、C 或 D；
• $d\in[1,n]$；
• dir=1 表示顺时针旋转，dir=0 表示逆时针旋转。

第二类操作格式

2 E d

其中：

• E 是棱 AB、AC、AD、BC、BD 或 CD，两个字母必须按字典序排列；
• $d\in\left[1,\left\lfloor\frac n2\right\rfloor\right]$。

格式示例

1 A 2 1   // 合法
1 D 3 0   // 合法
1 E 1 1   // 非法：不存在顶点 E
1 0 0     // 非法：格式错误
2 AB 1    // 合法
2 DA 3    // 非法：棱的两个字母未按字典序排列

输入样例 1

2 25000
1 2
1 3
4 2
4 6
6 5
5 3

输出样例 1

4
1 B 1 0
2 AC 1
1 A 1 0
1 D 2 0

样例解释

数据范围

测试点编号	$n\le$	$m=$	时间限制
1～2	$2$	$10^5$	1 秒
3～4	$3$
5～6	$10$	$2.5\times10^4$
7～8	$1000$
9～12		$10^5$	0.5 秒
13～16		$5\times10^4$
17～20		$2.5\times10^4$

对于全部数据：

$$2\le n\le 1000,\qquad m\ge 2.5\times10^4.$$

提示

原题下发了 checker.cpp，可用于检测输出是否合法。

在 Windows 环境下，编译得到 checker.exe 后，可以按以下方式运行：

checker.exe <input file> <output file> <answer file>

在 Linux 环境下，编译得到 checker 后，可以按以下方式运行：

./checker <input file> <output file> <answer file>

检查器可能给出以下信息：

• Too many operations.：构造步数超过限制；
• Length doesn't match.：实际输出的操作数与首行声明的操作数不一致；
• Undefined operation type.：操作类型不是 1 或 2；
• Undefined vertex.：输入了 A、B、C、D 之外的顶点；
• Illegal distance from vertex.：输入的 $d$ 不合法；
• Undefined rotation direction.：旋转方向不是 0 或 1；
• Illegal edge.：输入的棱格式错误或不存在；
• Wrong answer.：操作序列不能还原宇宙魔方；
• Accepted.：构造合法。

@下发文件