Farmer John có một xâu yêu thích \(t\) gồm \(M\) ký tự. Ông cũng có \(N\) xâu \(s_1,s_2,\ldots,s_N\), mỗi xâu gồm \(M\) ký tự (\(1\leq N,M\leq 1000\)).

FJ có thể thực hiện hai loại thao tác sau:

1. FJ chọn một xâu bất kỳ \(s_x\) và hai chỉ số \(p\), \(q\). Sau đó, ông hoán đổi ký tự thứ \(p\) và ký tự thứ \(q\) của \(s_x\) (\(1\le x\le N, 1\le p,q\le M\)).
2. FJ chọn hai xâu \(s_x\), \(s_y\) và một chỉ số \(k\). Sau đó, ông hoán đổi ký tự thứ \(k\) của \(s_x\) và ký tự thứ \(k\) của \(s_y\) (\(1\le x,y\le N, 1\le k\le M\)).

Mục tiêu của ông là biến \(s_1\) thành \(t\). Hãy tìm một dãy thao tác bất kỳ đạt được mục tiêu này. Vì FJ đang vội, ông chỉ có thời gian thực hiện tổng cộng tối đa \(2M\) thao tác. Dữ liệu vào đảm bảo có thể đạt được mục tiêu của FJ.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số lượng bộ test độc lập. Mỗi bộ test có định dạng sau:

Dòng đầu tiên chứa \(N\) và \(M\).

Dòng thứ hai chứa \(t\).

Tiếp theo là \(N\) dòng, dòng thứ \(i\) chứa \(s_i\).

Dữ liệu vào đảm bảo có thể đạt được mục tiêu của FJ. Tất cả các xâu chỉ chứa các chữ cái tiếng Anh viết thường (a-z).

Dữ liệu ra

Với mỗi bộ test, hãy xuất kết quả như sau:

Trên dòng đầu tiên, in một số nguyên \(K\), là số thao tác bạn sẽ thực hiện. \(K\) phải là một số nguyên không âm không vượt quá \(2M\).

Sau đó, in \(K\) dòng mô tả các thao tác bạn sẽ thực hiện theo thứ tự. Mỗi dòng phải có một trong hai dạng sau:

• 1 x p q
• 2 x y k

Ví dụ

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

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

nabana    Babana    baNaBa    banaNa
banana -> Nanana -> nanana -> nanaBa
nnbaaa    nnbaaa    nnbaaa    nnbaaa

Phân nhóm

• Dữ liệu 2-6: \(N,M\le 100\).
• Dữ liệu 7-12: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Bronze — Swap to Win. Tác giả: Chongtian Ma.
https://usaco.org/index.php?page=viewproblem2&cpid=1589