3. 交换致胜 (Swap to Win)

USACO 2026 第三场竞赛, 铜组

Farmer John 有一个他最喜欢的字符串 $t$，长度为 $M$。他还有 $N$ 个字符串 $s_1, s_2, \ldots, s_N$，每个长度也为 $M$ ($1 \leq N, M \leq 1000$)。

FJ 可以执行以下两种类型的操作：

1. FJ 选择任意一个字符串 $s_x$ 和两个下标 $p$ 和 $q$。然后，他交换 $s_x$ 中第 $p$ 个和第 $q$ 个字符 ($1\le x\le N, 1\le p,q\le M$)。
2. FJ 选择两个字符串 $s_x$ 和 $s_y$ 以及一个下标 $k$。然后，他交换 $s_x$ 和 $s_y$ 的第 $k$ 个字符 ($1\le x,y\le N, 1\le k\le M$)。

他的目标是使 $s_1$ 等于 $t$。请找出任意一系列能够达成目标的操作。由于 FJ 很匆忙，他总共只有时间执行 $2M$ 次操作。输入保证能够实现 FJ 的目标。

输入格式（从终端 / 标准输入读入）：

第一行包含 $T$ ($1\le T\le 10$)，表示独立测试用例的数量。每个测试用例的格式如下：

第一行包含 $N$ 和 $M$。

第二行包含 $t$。

接下来 $N$ 行，第 $i$ 行包含 $s_i$。

输入保证能够实现 FJ 的目标。所有字符串只包含小写英文字母（a-z）。

输出格式（输出至终端 / 标准输出）：

每个测试用例的输出格式如下：

第一行输出一个整数 $K$，表示你将执行的操作次数。$K$ 必须是一个非负整数，且小于等于 $2M$。

然后输出 $K$ 行，按顺序表示你将执行的操作。每行应为以下格式之一：

$\texttt{1 x p q}$ $\texttt{2 x y k}$

样例输入：

3
3 6
banana
nabana
banana
nnbaaa
5 3
abc
def
bca
ghi
jkl
mno
3 5
abcde
abcde
abcde
zzzzz

样例输出：

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

根据第一个测试用例的输出，$s$ 的变化过程如下（被交换的字母用大写表示）：

nabana    Babana    baNaBa    banaNa
banana -> Nanana -> nanana -> nanaBa
nnbaaa    nnbaaa    nnbaaa    nnbaaa

经过所有三次操作后，$s_1 = t$。

评分标准：

• 输入 2-6：$N, M \le 100$
• 输入 7-12：无额外限制。

题目来源：Chongtian Ma