P15572 [USACO26FEB] Swap to Win B

Farmer John has a favorite string $t$ with $M$ characters. He also has $N$ strings $s_1, s_2, \ldots, s_N$ each with $M$ characters ($1 \leq N, M \leq 1000$). FJ can perform the following two types of operations: - FJ chooses any string $s_x$ and two indices $p$ and $q$. Then, he swaps the $p$'th and $q$'th character of $s_x$ ($1\le x\le N, 1\le p,q\le M$). - FJ chooses two strings $s_x$ and $s_y$ and an index $k$. Then, he swaps the $k$'th characters of $s_x$ and $s_y$ ($1\le x,y\le N, 1\le k\le M$). His goal is to make $s_1$ equal to $t$. Find any series of operations that fulfills his goal. Because FJ is in a hurry, he only has time to perform a total of $2M$ operations. The inputs guarantee that it is possible to fulfill FJ's goal.

The first line contains $T$ ($1\le T\le 10$), the number of independent tests. Each test is specified in the following format: The first line contains $N$ and $M$. The second line contains $t$. Then, $N$ lines follow, the $i$'th of which contains $s_i$. The inputs will guarantee that it is possible to fulfill FJ's goal. All strings contain lowercase English letters (a-z).

The output for each test should be as follows: On the first line, output an integer $K$, the number of operations you will perform. $K$ must be a non-negative integer less than or equal to $2M$. Then, output $K$ lines, denoting the operations you will perform in sequential order. Each line should be one of the following: - $\texttt{1 x p q}$ - $\texttt{2 x y k}$

Here is how $s$ changes according to the first test's output (with letters swapped in uppercase): ``` nabana Babana baNaBa banaNa banana -> Nanana -> nanana -> nanaBa nnbaaa nnbaaa nnbaaa nnbaaa ``` After all three operations, $s_1=t$. ### SCORING: - Inputs 2-6: $N, M \le 100$ - Inputs 7-12: No additional constraints. Problem credits: Chongtian Ma