Swap to Win
Farmer John has a favorite string t with M characters. He also has N strings s1,s2,…,sN each with M characters (1≤N,M≤1000).
FJ can perform the following two types of operations:
- FJ chooses any string sx and two indices p and q. Then, he swaps the p'th and q'th character of sx (1≤x≤N,1≤p,q≤M).
- FJ chooses two strings sx and sy and an index k. Then, he swaps the k'th characters of sx and sy (1≤x,y≤N,1≤k≤M).
His goal is to make s1 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.
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, s1=t.
SCORING:
- Inputs 2-6: N,M≤100
- Inputs 7-12: No additional constraints.
Problem credits: Chongtian Ma
Source: USA Computing Olympiad.
Input Format
The first line contains T (1≤T≤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 si.
The inputs will guarantee that it is possible to fulfill FJ's goal. All strings contain lowercase English letters (a-z).
Output Format
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:
- 1 x p q
- 2 x y k