描述

农夫约翰拥有目标字符串 t（长度为 M）和 N 个长度均为 M 的字符串 s₁, s₂, ..., sₙ。他可以执行两类操作：

1. 类型 1：在某个字符串 sₓ 中交换第 p 位和第 q 位的字符（1 ≤ p, q ≤ M）；
2. 类型 2：在第 k 位（1 ≤ k ≤ M）上，交换两个不同字符串 sₓ 和 sᵧ 的该位置字符。 目标是通过至多 2M 次操作，使 s₁ 变为与 t 完全相同。保证有解。

输入输出格式

输入

第一行一个整数 T（测试用例数，1 ≤ T ≤ 10）。对每个测试用例：

• 第一行两个整数 N 和 M（1 ≤ N, M ≤ 1000）；
• 第二行一个长度为 M 的小写字符串 t；
• 接下来 N 行，每行一个长度为 M 的小写字符串 sᵢ（i = 1..N）。

输出

对每个测试用例：

• 第一行输出一个整数 K（操作总数，K ≤ 2M）；
• 接下来 K 行，每行描述一次操作：
  • 若为类型 1：输出 1 x p q，表示在 sₓ 中交换第 p 位与第 q 位（1-indexed）；
  • 若为类型 2：输出 2 x y k，表示交换 sₓ 与 sᵧ 在第 k 位上的字符（x ≠ y）。

样例

1
3 4
abcd
wxyz
pqrs
klmn

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

限制

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 1000
• 所有字符串均由小写字母组成
• 保证存在不超过 2M 次操作的可行解
• 输出操作数 K 必须满足 K ≤ 2M，且所有操作下标均合法（如 p,q ∈ [1,M]，x,y ∈ [1,N] 且 x≠y，k ∈ [1,M]）