USACO 2026 Third Contest, Bronze

Problem 3. Swap to Win


Contest has ended.

Log in to allow submissions in analysis mode


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:

  1. 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$).
  2. 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.

INPUT FORMAT (input arrives from the terminal / stdin):

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).

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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

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

Contest has ended. No further submissions allowed.