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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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
base1 = 1009
base2 = 1013
mask = (1 << 32) - 1
(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)
	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}')


base1 = 1009
base2 = 1013
mask = (1 << 32) - 1

def calculate_hash(f, r, c):
	global ph, pw, h
	tmp = [[0 for _ in range(c)] for _ in range(r)]
	(dr, dc) = (r - ph, c - pw)
	t1 = 1
	for _ in range(pw):
		t1 = t1 * base1 & mask
	for i in range(r):
		e = 0
		for j in range(pw):
			e = e * base1 + f[i][j]
		for j in range(dc):
			tmp[i][j] = e
			e = e * base1 - t1 * f[i][j] + f[i][j + pw] & mask
		tmp[i][dc] = e
	t2 = 1
	for _ in range(ph):
		t2 = t2 * base2 & mask
	for j in range(dc + 1):
		e = 0
		for i in range(ph):
			e = e * base2 + tmp[i][j]
		for i in range(dr):
			h[i][j] = e
			e = e * base2 - t2 * tmp[i][j] + tmp[i + ph][j] & mask
		h[dr][j] = e
(th, tw) = map(int, input().split())
t = [[ord(x) for x in input().strip()] for _ in range(th)]
(ph, pw) = map(int, input().split())
p = [[ord(x) for x in input().strip()] for _ in range(ph)]
if th >= ph and tw >= pw:
	h = [[0 for _ in range(tw)] for _ in range(th)]
	calculate_hash(p, ph, pw)
	key = h[0][0] & mask
	calculate_hash(t, th, tw)
	for i in range(th - ph + 1):
		for j in range(tw - pw + 1):
			if h[i][j] & mask == key:
				print(i, j)


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):

	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 = []
	for _ in range(h):
		m.append(input())
	(r, c) = [int(x) for x in input().split()]
	pt = []
	for _ in range(r):
		pt.append(input())
	sch = MatrixRKSearch(m, pt)
	result = []
	for (i, j) in sch.find():
		result.append((i, j))
	result.sort()
	for (i, j) in result:
		print(i, j)
run()


base1 = 1009
base2 = 1013
mask = (1 << 32) - 1

def calc_hash(f, r, c):
	global ph, pw, h
	tmp = [[0] * c for _ in range(r)]
	(dr, dc) = (r - ph, c - pw)
	t1 = base1 ** pw & mask
	for i in range(r):
		e = 0
		for j in range(pw):
			e = e * base1 + f[i][j]
		for j in range(dc):
			tmp[i][j] = e
			e = e * base1 - t1 * f[i][j] + f[i][j + pw] & mask
		tmp[i][dc] = e
	t2 = 1
	for _ in range(ph):
		t2 = t2 * base2 & mask
	for j in range(dc + 1):
		e = 0
		for i in range(ph):
			e = e * base2 + tmp[i][j]
		for i in range(dr):
			h[i][j] = e
			e = e * base2 - t2 * tmp[i][j] + tmp[i + ph][j] & mask
		h[dr][j] = e
(th, tw) = map(int, input().split())
t = tuple((tuple((ord(c) for c in input())) for _ in range(th)))
(ph, pw) = map(int, input().split())
p = tuple((tuple((ord(c) for c in input())) for _ in range(ph)))
ans = []
if th >= ph and tw >= pw:
	h = [[0] * tw for _ in range(th)]
	calc_hash(p, ph, pw)
	key = h[0][0] & mask
	calc_hash(t, th, tw)
	for i in range(th - ph + 1):
		for j in range(tw - pw + 1):
			if h[i][j] & mask == key:
				ans.append(f'{i} {j}')
if ans:
	print('\n'.join((a for a in ans)))


from collections import deque
import re
import sys
sys.setrecursionlimit(100000)

class AC:

	def __init__(self, num, parent, char):
		self.num = num
		self.parent = parent
		self.char = char
		self.d = {}
		self.failure = None

	def insert(self, string, num):
		if not string[0] in self.d:
			self.d[string[0]] = AC(num, self, string[0])
			num += 1
		if not string[1:] == '':
			return self.d[string[0]].insert(string[1:], num)
		else:
			return num

	def setFailure(self):
		tmp = self.parent.failure
		while True:
			if self.char in tmp.d:
				self.failure = tmp.d[self.char]
				break
			elif tmp.num == 0:
				self.failure = tmp
				break
			else:
				tmp = tmp.failure

	def setFailureRoot(self):
		self.failure = self

	def setFailureFirstLayer(self):
		self.failure = self.parent

	def transition(self, string):
		if string == '':
			return []
		elif string[0] in self.d:
			tmp = self.d[string[0]]
			num = '{0:09d}'.format(tmp.num)
			return [num] + tmp.transition(string[1:])
		elif self.num == 0:
			num = '{0:09d}'.format(self.num)
			return [num] + self.transition(string[1:])
		else:
			return self.failure.transition(string)
(H, W) = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
(R, C) = [int(i) for i in input().split()]
B = [input() for _ in range(R)]
root = AC(0, None, '')
root.setFailureRoot()
num = 1
for i in B:
	num = root.insert(i, num)
d = deque()
for i in root.d.values():
	i.setFailureFirstLayer()
	for j in i.d.values():
		d.appendleft(j)
while len(d) > 0:
	tmp = d.pop()
	tmp.setFailure()
	for i in tmp.d.values():
		d.appendleft(i)
trans = ['' for i in range(W)]
for i in A:
	tmp = root.transition(i)
	for (j, k) in enumerate(tmp):
		trans[j] = trans[j] + k + '#'
ans = ''
for i in B:
	ans = ans + root.transition(i)[-1] + '#'
ansd = deque()
for (i, j) in enumerate(trans):
	obj = re.search(ans, j)
	c = 0
	while obj:
		s = obj.start()
		if i - C + 1 < 0:
			print(i)
		ansd.append(((c + s) // 10, i - C + 1))
		obj = re.search(ans, j[c + s + 10:])
		c += s + 10
for i in sorted(ansd):
	print(i[0], i[1])


import sys
readline = sys.stdin.readline
write = sys.stdout.write
mod = 10 ** 9 + 9
p = 13
q = 19
p_table = q_table = None

def prepare(L):
	global p_table, q_table
	p_table = [1] * (L + 1)
	q_table = [1] * (L + 1)
	for i in range(L):
		p_table[i + 1] = p_table[i] * p % mod
		q_table[i + 1] = q_table[i] * q % mod

def rolling_hash(S, W, H):
	D = [[0] * (W + 1) for i in range(H + 1)]
	for i in range(H):
		su = 0
		dp = D[i]
		di = D[i + 1]
		si = S[i]
		for j in range(W):
			v = si[j]
			su = (su * p + v) % mod
			di[j + 1] = (su + dp[j + 1] * q) % mod
	return D

def get(S, x0, y0, x1, y1):
	P = p_table[x1 - x0]
	Q = q_table[y1 - y0]
	return (S[y1][x1] - S[y1][x0] * P - S[y0][x1] * Q + S[y0][x0] * (P * Q) % mod) % mod

def solve():
	prepare(1001)
	(H, W) = map(int, readline().split())
	M = [list(map(ord, readline().strip())) for i in range(H)]
	(R, C) = map(int, readline().split())
	M0 = [list(map(ord, readline().strip())) for i in range(R)]
	rh = rolling_hash(M, W, H)
	rh0 = rolling_hash(M0, C, R)
	v = rh0[-1][-1]
	for i in range(H - R + 1):
		for j in range(W - C + 1):
			if v == get(rh, j, i, j + C, i + R):
				write('%d %d\n' % (i, j))
solve()


base1 = 127
base2 = 1009
mask = (1 << 32) - 1

def calc_hash(f, r, c):
	global ph, pw, h
	tmp = [[0] * c for _ in range(r)]
	(dr, dc) = (r - ph, c - pw)
	t1 = 1
	for _ in range(pw):
		t1 = t1 * base1 & mask
	for i in range(r):
		e = 0
		for j in range(pw):
			e = e * base1 + f[i][j]
		for j in range(dc):
			tmp[i][j] = e
			e = e * base1 - t1 * f[i][j] + f[i][j + pw] & mask
		tmp[i][dc] = e
	t2 = 1
	for _ in range(ph):
		t2 = t2 * base2 & mask
	for j in range(dc + 1):
		e = 0
		for i in range(ph):
			e = e * base2 + tmp[i][j]
		for i in range(dr):
			h[i][j] = e
			e = e * base2 - t2 * tmp[i][j] + tmp[i + ph][j] & mask
		h[dr][j] = e
(th, tw) = map(int, input().split())
t = [[ord(c) for c in input().strip()] for _ in range(th)]
(ph, pw) = map(int, input().split())
p = [[ord(c) for c in input().strip()] for _ in range(ph)]
if th >= ph and tw >= pw:
	h = [[0] * tw for _ in range(th)]
	calc_hash(p, ph, pw)
	key = h[0][0] & mask
	calc_hash(t, th, tw)
	for i in range(th - ph + 1):
		for j in range(tw - pw + 1):
			if h[i][j] & mask == key:
				print(i, j)


base1 = 1009
base2 = 1013
mask = (1 << 32) - 1

def calc_hash(f, r, c):
	global ph, pw, h
	tmp = [[0] * c for _ in range(r)]
	(dr, dc) = (r - ph, c - pw)
	t1 = 1
	for _ in range(pw):
		t1 = t1 * base1 & mask
	for i in range(r):
		e = 0
		for j in range(pw):
			e = e * base1 + f[i][j]
		for j in range(dc):
			tmp[i][j] = e
			e = e * base1 - t1 * f[i][j] + f[i][j + pw] & mask
		tmp[i][dc] = e
	t2 = 1
	for _ in range(ph):
		t2 = t2 * base2 & mask
	for j in range(dc + 1):
		e = 0
		for i in range(ph):
			e = e * base2 + tmp[i][j]
		for i in range(dr):
			h[i][j] = e
			e = e * base2 - t2 * tmp[i][j] + tmp[i + ph][j] & mask
		h[dr][j] = e
(th, tw) = map(int, input().split())
t = tuple((tuple((ord(c) for c in input())) for _ in range(th)))
(ph, pw) = map(int, input().split())
p = tuple((tuple((ord(c) for c in input())) for _ in range(ph)))
if th >= ph and tw >= pw:
	h = [[0] * tw for _ in range(th)]
	calc_hash(p, ph, pw)
	key = h[0][0] & mask
	calc_hash(t, th, tw)
	for i in range(th - ph + 1):
		for j in range(tw - pw + 1):
			if h[i][j] & mask == key:
				print(i, j)


base1 = 1009
base2 = 1013
mask = (1 << 32) - 1

def calc_hash(f, r, c):
	global ph, pw, h
	tmp = [[0] * c for _ in range(r)]
	(dr, dc) = (r - ph, c - pw)
	t1 = 1
	for _ in range(pw):
		t1 = t1 * base1 & mask
	for i in range(r):
		e = 0
		for j in range(pw):
			e = e * base1 + f[i][j]
		for j in range(dc):
			tmp[i][j] = e
			e = e * base1 - t1 * f[i][j] + f[i][j + pw] & mask
		tmp[i][dc] = e
	t2 = 1
	for _ in range(ph):
		t2 = t2 * base2 & mask
	for j in range(dc + 1):
		e = 0
		for i in range(ph):
			e = e * base2 + tmp[i][j]
		for i in range(dr):
			h[i][j] = e
			e = e * base2 - t2 * tmp[i][j] + tmp[i + ph][j] & mask
		h[dr][j] = e
(th, tw) = map(int, input().split())
t = tuple((tuple((ord(c) for c in input())) for _ in range(th)))
(ph, pw) = map(int, input().split())
p = tuple((tuple((ord(c) for c in input())) for _ in range(ph)))
ans = []
if th >= ph and tw >= pw:
	h = [[0] * tw for _ in range(th)]
	calc_hash(p, ph, pw)
	key = h[0][0] & mask
	calc_hash(t, th, tw)
	for i in range(th - ph + 1):
		for j in range(tw - pw + 1):
			if h[i][j] & mask == key:
				ans.append(f'{i} {j}')
if ans:
	print('\n'.join((a for a in ans)))


base1 = 1009
base2 = 1013
mask = (1 << 32) - 1

def calc_hash(f, r, c):
	global ph, pw, h
	tmp = [[0] * c for _ in range(r)]
	(dr, dc) = (r - ph, c - pw)
	t1 = 1
	for _ in range(pw):
		t1 = t1 * base1 & mask
	for i in range(r):
		e = 0
		for j in range(pw):
			e = e * base1 + f[i][j]
		for j in range(dc):
			tmp[i][j] = e
			e = e * base1 - t1 * f[i][j] + f[i][j + pw] & mask
		tmp[i][dc] = e
	t2 = 1
	for _ in range(ph):
		t2 = t2 * base2 & mask
	for j in range(dc + 1):
		e = 0
		for i in range(ph):
			e = e * base2 + tmp[i][j]
		for i in range(dr):
			h[i][j] = e
			e = e * base2 - t2 * tmp[i][j] + tmp[i + ph][j] & mask
		h[dr][j] = e
(th, tw) = map(int, input().split())
t = [[ord(c) for c in input().strip()] for _ in range(th)]
(ph, pw) = map(int, input().split())
p = [[ord(c) for c in input().strip()] for _ in range(ph)]
if th >= ph and tw >= pw:
	h = [[0] * tw for _ in range(th)]
	calc_hash(p, ph, pw)
	key = h[0][0] & mask
	calc_hash(t, th, tw)
	for i in range(th - ph + 1):
		for j in range(tw - pw + 1):
			if h[i][j] & mask == key:
				print(i, j)


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)

	@lru_cache(maxsize=1000)
	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 run():
	(h, w) = [int(x) for x in input().split()]
	m = []
	for _ in range(h):
		m.append(input())
	(r, c) = [int(x) for x in input().split()]
	pt = []
	for _ in range(r):
		pt.append(input())
	sch = MatrixRKSearch(m, pt)
	result = []
	for (i, j) in sch.find():
		result.append((i, j))
	result.sort()
	for (i, j) in result:
		print(i, j)
run()