Nežmah 씨는 $0$과 $1$로 채워진 $n$행 $m$열의 격자를 발견했습니다. 강박증 때문에 그는 격자에 있는 모든 $1$을 $0$으로 바꾸고 싶어 합니다. 그에게는 자신이 좋아하는 $k$개의 순서쌍 $(a_i, b_i)$가 있습니다. 그가 할 수 있는 유일한 연산은 다음과 같습니다:

• 첫 번째 행이나 첫 번째 열 내부에 있는 칸 $(r, c)$를 하나 선택합니다.
• 그가 좋아하는 수의 쌍 $(a, b)$를 하나 선택합니다.
• 칸 $(r, c)$를 왼쪽 위 모서리로 하고 높이가 $a$, 너비가 $b$인 직사각형에 포함된 모든 칸 내부의 숫자를 뒤집습니다. 뒤집는다는 것은 모든 $0$을 $1$로, 모든 $1$을 $0$으로 바꾸는 것을 의미합니다. 직사각형은 격자 내부에 완전히 포함되어야 합니다.

Nežmah가 격자를 깨끗이 비울 수 있도록 도와주세요!

입력

첫 번째 줄에는 테스트 케이스의 개수를 나타내는 단일 정수 $t$ ($1 \le t \le 300$)가 포함됩니다.

각 테스트 케이스의 첫 번째 줄에는 격자의 크기와 쌍 $(a_i, b_i)$의 개수를 나타내는 $3$개의 정수 $n$, $m$, $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$)가 포함됩니다.

다음 $n$개의 줄에는 각각 모두 0 또는 1로 이루어진 $m$개의 문자가 포함되어 격자를 설명합니다.

다음 $k$개의 줄에는 각각 두 정수 $a_i$와 $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, 모든 쌍 $(a_i, b_i)$는 서로 다름)가 포함됩니다.

모든 테스트 케이스에서 $n$의 합과 $m$의 합은 각각 $1000$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해, 연산의 횟수 ($0 \le op \le k(n + m)$)를 출력합니다.

다음 $op$개의 줄에는 각각 $3$개의 정수 $r_i$, $x_i$, $y_i$ ($1 \le r_i \le k, 1 \le x_i \le n - a_{r_i} + 1, 1 \le y_i \le m - b_{r_i} + 1$, $x_i$와 $y_i$ 중 적어도 하나는 $1$과 같음)를 출력합니다. 이는 왼쪽 위 모서리가 $(x_i, y_i)$이고 $a_{r_i}$개의 행과 $b_{r_i}$개의 열을 가진 직사각형 내부의 모든 칸을 뒤집기로 선택했음을 의미합니다.

해가 항상 존재함이 보장되며, 해가 여러 개라면 그중 아무것이나 출력해도 됩니다.

예제

입력 1

5
6 6 2
000000
111110
000000
100001
011111
111110
5 5
3 5
4 5 2
10111
00101
10000
01100
1 3
2 1
2 2 1
00
00
1 1
5 5 3
10100
10010
00000
01101
00100
3 4
2 3
4 2
5 5 4
01010
01010
10101
00100
00100
2 2
2 3
3 2
3 3

출력 1

5
1 1 2
2 1 2
2 2 1
2 3 1
2 4 1
6
1 1 1
1 1 2
1 4 1
2 1 3
2 1 5
2 3 1
0
10
1 1 1
1 1 2
1 2 1
2 1 1
2 1 2
2 4 1
3 1 1
3 1 2
3 1 4
3 2 1
5
3 1 4
2 1 3
4 1 2
2 4 1
3 3 1