human
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
Solve the task in PYTHON3.

Can you provide a Python program to find places where a R × C pattern is found within a H × W region?
assistant
#Here is Python program to find places where a R × C pattern is found within a H × W region.

from functools import lru_cache

class MatrixRKSearch:
    shift = 40
    size = 33554393

    def __init__(self, m1, m2):
        self.haystack = self._encode(m1)
        self.needle = self._encode(m2)

    def find(self):
        i1, j1 = len(self.haystack), len(self.haystack[0])
        i2, j2 = len(self.needle), len(self.needle[0])
        if i1 < i2 or j1 < j2:
            return

        hs1 = [self._hash(s, j2) for s in self.haystack]
        hs2 = [self._hash(s, j2) for s in self.needle]
        dm = self.shift**(j2-1) % self.size

        for j in range(j1-j2+1):
            for i in range(i1-i2+1):
                if hs1[i:i+i2] == hs2:
                    yield (i, j)
            if j+j2 < j1:
                for i in range(i1):
                    hs1[i] = self._shift(hs1[i], self.haystack[i][j+j2],
                                         self.haystack[i][j], dm)

    def _shift(self, h, add, remove, dm):
        return ((h - remove*dm) * self.shift + add) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, m):
        basea = ord('a')
        based = ord('0')
        es = []
        for s in m:
            bs = []
            for c in s:
                if c.isdigit():
                    bs.append(ord(c) - based + 27)
                else:
                    bs.append(ord(c) - basea)
            es.append(bs)

        return es

def search(matrix, pattern):
    """Search matrix for pattern
    """
    def _check(y, x):
        for m in range(py):
            for n in range(px):
                if matrix[y+m][x+n] != pattern[m][n]:
                    return False
        return True

    mx = len(matrix[0])
    my = len(matrix)
    px = len(pattern[0])
    py = len(pattern)
    for i in range(my-py+1):
        for j in range(mx-px+1):
            if _check(i, j):
                yield (i, j)

def run():
    h, w = [int(x) for x in input().split()]
    m = []

  ...