题目描述

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}$

样例

样例输入 1

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

样例输出 1

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：无额外限制。