Cipher

While exploring the Universe, a space agency found traces of extraterrestrial (ET) intelligence: a collection of rectangular metal plates carrying messages written in an alien language.

Each plate holds a 2D array with $n$ rows and $m$ columns. Every cell is a printable ASCII character whose numeric code lies in the range $32 \dots 127$. Each plate also carries two integers, $a$ and $b$.

The researchers concluded that a message can be decrypted with a cipher: a key, hidden inside the plate's array, that reveals how to read the message. The cipher is the $a \times b$ rectangular subarray of the message that occurs exactly $k$ times, with $k \ge 3$. Occurrences of the cipher may overlap. It is guaranteed that no other $a \times b$ subarray occurs more than $k - 2$ times, so the cipher is unique.

For example, suppose the array is $8 \times 10$ ($n = 8$, $m = 10$), the cipher size is $3 \times 3$ ($a = 3$, $b = 3$), and the cipher occurs $5$ times ($k = 5$). Then no other $3 \times 3$ subarray of this array occurs more than $3$ times.

Given the array that represents the message and the integers $a$ and $b$ written on the plate, find the cipher and all positions on the plate where it occurs.

The first line contains two integers $n$ and $m$, separated by a space. Each of the next $n$ lines contains a string of exactly $m$ characters; the $i$-th of these lines is row $i$ of the array. The last line contains the two integers $a$ and $b$, separated by a space.

On the first line print the integers $a$ and $b$, separated by a space (exactly the values from the input). Then print $a$ lines, each a string of $b$ characters, giving the cipher. On the next line print the integer $k$, the number of times the cipher occurs in the array. Then print $k$ lines, each containing two integers: the row and the column (1-indexed) of the upper-left corner of one occurrence of the cipher. Print these $k$ pairs sorted in increasing order of row, breaking ties by increasing column.

• $5 \le n, m \le 1000$
• $2 \le a \le n$
• $2 \le b \le m$
• $3 \le k \le 1000$
• Rows and columns are numbered from $1$, starting at the upper-left corner.

An example array, with the four occurrences of its cipher highlighted, is shown below: