암호

한 우주 기관이 우주를 탐사하던 중 외계 지성의 흔적을 발견했다. 바로 외계 언어로 쓰인 메시지가 담긴 직사각형 금속판 여러 장이다.

각 금속판에는 $n$개의 행과 $m$개의 열로 이루어진 2차원 배열이 새겨져 있다. 배열의 각 칸은 출력 가능한 ASCII 문자이며, 그 문자 코드는 $32 \dots 127$ 범위에 속한다. 또한 각 금속판에는 두 정수 $a$와 $b$가 함께 적혀 있다.

연구진은 각 메시지가 암호로 해독될 수 있음을 알아냈다. 암호란 메시지를 읽는 방법을 알려 주는 열쇠로, 금속판의 배열 속에 숨겨져 있다. 암호는 배열에서 정확히 $k$번 나타나는 $a \times b$ 크기의 직사각형 부분 배열이며, $k \ge 3$이다. 암호가 나타나는 위치들은 서로 겹칠 수 있다. 그리고 다른 어떤 $a \times b$ 부분 배열도 $k - 2$번을 초과해 나타나지 않음이 보장되므로, 암호는 유일하게 결정된다.

예를 들어 배열이 $8 \times 10$이고($n = 8$, $m = 10$), 암호의 크기가 $3 \times 3$이며($a = 3$, $b = 3$), 암호가 $5$번 나타난다면($k = 5$), 이 배열의 다른 어떤 $3 \times 3$ 부분 배열도 $3$번을 초과해 나타나지 않는다.

메시지를 나타내는 배열과 금속판에 적힌 두 정수 $a$, $b$가 주어질 때, 암호와 암호가 나타나는 모든 위치를 찾아라.

첫째 줄에 두 정수 $n$과 $m$이 공백으로 구분되어 주어진다. 이어지는 $n$개의 줄에는 각각 정확히 $m$개의 문자로 이루어진 문자열이 주어지며, 그중 $i$번째 줄은 배열의 $i$번째 행을 나타낸다. 마지막 줄에는 두 정수 $a$와 $b$가 공백으로 구분되어 주어진다.

첫째 줄에 두 정수 $a$와 $b$를 공백으로 구분하여 출력한다(입력으로 주어진 값과 정확히 같아야 한다). 이어서 $a$개의 줄에 걸쳐 각 줄마다 $b$개의 문자로 이루어진 문자열로 암호를 출력한다. 그다음 줄에는 암호가 배열에 나타나는 횟수인 정수 $k$를 출력한다. 마지막으로 $k$개의 줄에 걸쳐 각 줄마다 두 정수를 출력하는데, 이는 암호가 나타나는 한 위치의 왼쪽 위 모서리의 행과 열(1부터 시작)을 나타낸다. 이 $k$개의 쌍은 행이 증가하는 순서로 정렬하여 출력하며, 행이 같으면 열이 증가하는 순서로 정렬한다.

• $5 \le n, m \le 1000$
• $2 \le a \le n$
• $2 \le b \le m$
• $3 \le k \le 1000$
• 행과 열의 번호는 왼쪽 위 모서리에서 시작하여 $1$부터 매긴다.

아래 그림은 한 배열과, 그 배열에서 강조 표시된 암호의 네 번의 등장을 보여 준다.