问题 3. 交换以获胜 (Swap to Win)

USACO 2026 第三次竞赛，Bronze 组

农夫约翰有一个他最喜欢的长度为 $M$ 的字符串 $t$。他还有 $N$ 个长度都为 $M$ 的字符串 $s_1, s_2, \ldots, s_N$（$1 \le N, M \le 1000$）。

农夫约翰可以执行以下两种类型的操作：

1. 农夫约翰选择任意一个字符串 $s_x$ 和两个索引 $p$ 和 $q$。然后，他交换 $s_x$ 的第 $p$ 个和第 $q$ 个字符（$1 \le x \le N, 1 \le p, q \le M$）。
2. 农夫约翰选择两个字符串 $s_x$ 和 $s_y$ 以及一个索引 $k$。然后，他交换 $s_x$ 和 $s_y$ 的第 $k$ 个字符（$1 \le x, y \le N, 1 \le k \le M$）。

他的目标是使 $s_1$ 等于 $t$。请找出任何一个能实现他目标的操作序列。由于农夫约翰很着急，他最多只能执行总共 $2M$ 次操作。输入保证一定可以实现农夫约翰的目标。所有字符串都包含小写英文字母 (a-z)。

输入格式 (输入从终端/stdin接收):

第一行包含 $T$（$1 \le T \le 10$），即独立测试用例的数量。 每个测试用以下格式指定：

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

第二行包含目标字符串 $t$。

接着是 $N$ 行，第 $i$ 行包含字符串 $s_i$。

输入保证可以实现目标。所有字符串都包含小写英文字母 (a-z)。

输出格式 (输出到终端/stdout):

对于每个测试用例，在单独的一行上输出以下内容：

在第一行，输出一个整数 $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