Grid Pattern Search

You are given a 2D grid of characters and a pattern of characters. Your task is to find all occurrences of the pattern in the grid, searching both row-wise and column-wise.

A match is found in a row if the contiguous sequence of characters matches the given pattern exactly. Similarly, a match is found in a column if reading the characters top-down in that column yields the pattern as a contiguous sequence.

For example, if the grid is a \(m \times n\) matrix and the pattern has length \(p\), then a match in a row occurs if there exists an index \(i\) (with \(0 \leq i \leq n-p\)) such that:

\[ grid[row][i..i+p-1] = pattern \]

Similarly for a column. The output should list each occurrence with the type (either row or column) followed by the 0-based index of the row or column where the match is found. The order is all row matches first (in increasing row order) followed by column matches (in increasing column order).

inputFormat

The input is read from standard input and has the following format:

 m n
 row_1
 row_2
 ...
 row_m
 p
 pattern

Here:

• m and n are integers representing the number of rows and columns in the grid.
• Each of the next m lines contains a string of exactly n characters representing a row of the grid.
• p is an integer representing the length of the pattern.
• The following line is a string of p characters representing the pattern to search for.

outputFormat

The output is printed to standard output. For each match, output a line containing two tokens separated by a space:

Here, type is either row or column, and index is the 0-based index of the row or column in which the pattern is found. If no occurrence is found, no output is produced.

## sample

3 3
ABC
DEF
GHI
2
BC

row 0

</p>