King's Walk

A chess king wants to take a walk across the Spring Field. The field is a rectangle, and every cell holds one lowercase Latin letter.

The king starts the walk on any cell of the field and makes $n-1$ moves. Each move follows the chess rule for a king: he steps to a cell that shares an edge or a corner with the current cell. Staying on the same cell does not count as a move. The king may visit the same cell several times during the walk.

The king therefore visits $n$ cells. Reading the letters of those cells in visiting order gives a string $s$ of length $n$.

In the evening the king compares this string with the motto of his dynasty, which is also exactly $n$ letters long. If position $i$ of the motto and position $i$ of $s$ hold the same letter, the king promotes the $i$-th pawn.

Find a route that promotes as many pawns as possible.

The first line contains two integers $h$ and $w$ ($2 \le h, w \le 20$), the size of the field.

Each of the next $h$ lines contains $w$ lowercase Latin letters, the description of the field.

The next line contains an integer $n$ ($1 \le n \le 50$).

The last line contains the motto of the dynasty, a string of $n$ lowercase Latin letters.

Print $m$, the largest possible number of promoted pawns, on the first line.

On each of the next $n$ lines print the coordinates of one visited cell, in visiting order: the row number and the column number separated by a space. Rows are numbered from top to bottom starting at 1, and columns from left to right starting at 1.

If several routes promote $m$ pawns, print the lexicographically smallest one. Compare routes as the sequence of coordinates in visiting order, $r_1, c_1, r_2, c_2, \dots, r_n, c_n$.