Mosaic Motif Detection

The International Center for the Preservation of Ceramics (ICPC) defines a mosaic as a rectangular grid where each grid square contains a colored tile, and a motif is a similar grid where some squares can be empty. Formally, a motif of size (r_p \times c_p) appears in a mosaic of size (r_q \times c_q) at position ((r, c)) if for every (1 \le i \le r_p) and (1 \le j \le c_p), the corresponding mosaic tile at ((r+i-1, c+j-1)) exists and either the motif cell is empty or its color matches the mosaic tile. In the input, the motif is given first. The motif grid is represented by (r_p) lines of exactly (c_p) characters, where a dot ('.') denotes an empty cell (wildcard) and any other character represents a colored tile. The mosaic is given subsequently in the same format (without wildcards, as every cell is colored).

Your task is to find all occurrences of the motif in the mosaic. An occurrence is defined by the top‐left position in the mosaic at which the motif appears exactly (in the sense described above). The positions are 1-indexed. If the motif occurs, first output the total number of occurrences, then output each occurrence on a separate line as two integers (row and column).

inputFormat

The first line contains two integers (r_p) and (c_p) denoting the number of rows and columns of the motif. The following (r_p) lines each contain a string of length (c_p). A dot ('.') in the motif denotes an empty cell.

The next line contains two integers (r_q) and (c_q) representing the number of rows and columns of the mosaic. The following (r_q) lines each contain a string of length (c_q) representing the mosaic (every cell is colored).

outputFormat

First, output an integer representing the number of occurrences of the motif in the mosaic. Then, for each occurrence, output a line with two integers representing the row and column of the top‐left cell of the matching subgrid in the mosaic. The occurrences should be listed in order of increasing row, and for the same row, increasing column.

sample

1 1
A
3 3
ABA
BAA
AAA

7
1 1
1 3
2 2
2 3
3 1
3 2
3 3