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.
INPUT FORMAT (input arrives from the terminal / stdin):
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 (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:
1 x p q
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, s1=t
.
SCORING:
Inputs 2-6: N,M≤100
Inputs 7-12: No additional constraints.
Problem credits: Chongtian Ma