문제

성현이는 길이가 $M$인 문자열 $t$를 가장 좋아한다. 또한, 성현이는 각각 길이가 $M$인 $N$개의 문자열 $s_1, s_2, \ldots, s_N$을 가지고 있다. ($1 \le N, M \le 1\,000$)

성현이는 다음과 같은 두 가지 연산을 수행할 수 있다.

1. 성현이는 문자열 $s_x$를 선택하고, $p$번째 문자와 $q$번째 문자를 서로 바꾼다. ($1 \le x \le N, 1 \le p, q \le M$)
2. 성현이는 두 문자열 $s_x$와 $s_y$를 선택하고, 각각의 $k$번째 문자를 서로 바꾼다. ($1 \le x, y \le N, 1 \le k \le M$)

성현이의 목표는 $s_1$을 $t$와 동일하게 만드는 것이다. 목표를 달성하기 위한 연산 과정을 하나 찾으시오. 성현이는 매우 바쁘기 때문에, 최대 $2M$번의 연산만 수행할 수 있다. 항상 목표를 달성할 수 있는 입력만 주어진다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10$) 각 테스트 케이스는 다음과 같은 형식으로 주어진다.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 문자열 $t$가 주어진다.

이어서 $N$개의 줄에 걸쳐 $s_1, s_2, \ldots, s_N$이 한 줄에 하나씩 주어진다.

항상 목표를 달성할 수 있는 입력만 주어지며, 모든 문자열은 영어 소문자(a-z)로만 이루어져 있다.

출력

각 테스트 케이스마다 다음과 같이 출력한다.

첫째 줄에 수행할 연산의 횟수 $K$를 출력한다. ($0 \le K \le 2M$)

이어서 $K$개의 줄에 걸쳐 수행할 연산을 순서대로 출력한다. 각 연산은 다음과 같은 형식 중 하나여야 한다.

• 1 x p q
• 2 x y k

예제 입력 1

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

예제 출력 1

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

제약 사항

• 데이터 2-6: $N, M \le 100$
• 데이터 7-12: 추가적인 제약 사항이 없다.