p02249 Pattern Search
Find places where a R × C pattern is found within a H × W region. Print top-left coordinates (i, j) of sub-regions where the pattern found. The top-left and bottom-right coordinates of the region is (0, 0) and (H-1, W-1) respectively.

Constraints

* 1 ≤ H, W ≤ 1000
* 1 ≤ R, C ≤ 1000
* The input consists of alphabetical characters and digits

Input

In the first line, two integers H and W are given. In the following H lines, i-th lines of the region are given.

In the next line, two integers R and C are given. In the following R lines, i-th lines of the pattern are given.

Example

Input

4 5
00010
00101
00010
00100
3 2
10
01
10


Output

0 3
1 2
```python
from typing import List


def calc_hash(tab: List[List[int]], row_num: int, col_num: int) -> None:
    global hash_table, R, C, baes1, base2, mask
    tmp_table = [[0] * col_num for _ in range(row_num)]
    diff_row, diff_col = row_num - R, col_num - C

    bit_mask = 1
    for _ in range(C):
        bit_mask = (bit_mask * base1) & mask
    for r in range(row_num):
        hash_v = 0
        for c in range(C):
            hash_v = hash_v * base1 + tab[r][c]
        for dc in range(diff_col):
            tmp_table[r][dc] = hash_v
            hash_v = (hash_v * base1 - bit_mask * tab[r][dc] + tab[r][dc + C]) & mask
        tmp_table[r][diff_col] = hash_v

    bit_mask = 1
    for _ in range(R):
        bit_mask = (bit_mask * base2) & mask
    for c in range(diff_col + 1):
        hash_v = 0
        for r in range(R):
            hash_v = hash_v * base2 + tmp_table[r][c]
        for dr in range(diff_row):
            hash_table[dr][c] = hash_v
            hash_v = (hash_v * base2 - bit_mask * tmp_table[dr][c]
                      + tmp_table[dr + R][c]) & mask
        hash_table[diff_row][c] = hash_v


if __name__ == "__main__":
    base1 = 1009  # The first prime number over 1000.
    base2 = 1013  # The second prime number over 1000.
    mask = (1 << 32) - 1  # Mask.

    H, W = map(lambda x: int(x), input().split())
    region = [[0] * W for _ in range(H)]
    for row in range(H):
        region[row] = [ord(s) for s in input()]

    R, C = map(lambda x: int(x), input().split())
    pattern = [[0] * C for _ in range(R)]
    for row in range(R):
        pattern[row] = [ord(s) for s in input()]

    if H >= R and W >= C:
        hash_table = [[0] * W for _ in range(H)]
        calc_hash(pattern, R, C)  # Calc the target hash and save it into hash_table[0][0]
        key = hash_table[0][0] & mask
        calc_hash(region, H, W)
        for r in range(H - R + 1):
            for c in range(W - C + 1):
                if key == hash_table[r][c] & mask:
                    print(f"{r} {c}")


```