Hoán Đổi Để Thắng

Bác John có một chuỗi mục tiêu $t$ gồm $M$ ký tự và $N$ chuỗi $s_1,s_2,\dots ,s_N$, mỗi chuỗi gồm $M$ ký tự (đều là chữ cái tiếng Anh thường).

Có hai phép biến đổi:

1. Hoán vị trong chuỗi: Chọn chuỗi $s_x$ và hai vị trí $p,q$. Hoán đổi ký tự thứ $p$ và thứ $q$ của $s_x$.
2. Hoán vị giữa hai chuỗi: Chọn hai chuỗi $s_x,s_y$ và vị trí $k$. Hoán đổi ký tự thứ $k$ của $s_x$ và $s_y$.

Biến đổi $s_1$ thành $t$ sử dụng tối đa $2M$ phép biến đổi. Đảm bảo luôn tồn tại lời giải.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số bộ test ($1\le T\le 10$)
• Với mỗi bộ test:
  • Dòng 1: Hai số nguyên $N$ và $M$
  • Dòng 2: Chuỗi mục tiêu $t$
  • $N$ dòng tiếp theo: Các chuỗi $s_1,s_2,\dots ,s_N$

Dữ liệu ra

Với mỗi bộ test:

• Dòng 1: Số nguyên $K$ ($0\le K\le 2M$) — số phép biến đổi
• $K$ dòng tiếp theo: Mỗi dòng mô tả một phép biến đổi theo định dạng 1 x p q hoặc 2 x y k

Ràng buộc

• $1\le N,M\le 1000$
• Tất cả chuỗi gồm chữ cái tiếng Anh thường
• Luôn tồn tại lời giải

Ví dụ

Ghi chú

• Test 2-6: $N,M\le 100$
• Test 7-12: Không ràng buộc bổ sung