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

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdio>

using namespace std;

template <unsigned long long MOD = 1000000007, unsigned long long base = 2009>
struct RollingHash {
	vector<unsigned long long> hash, power;

	RollingHash() {}
	RollingHash(const string& s) {
		int n = s.size();
		hash.assign(n + 1, 0);
		power.assign(n + 1, 1);
		for (int i = 0; i < n; ++i) {
			hash[i + 1] = (hash[i] * base + s[i]) % MOD;
			power[i + 1] = power[i] * base % MOD;
		}
	}
	RollingHash(vector<unsigned long long> si) {
		int n = si.size();
		hash.assign(n + 1, 0);
		power.assign(n + 1, 1);
		for (int i = 0; i < n; ++i) {
			hash[i + 1] = (hash[i] * base + si[i]) % MOD;
			power[i + 1] = power[i] * base % MOD;
		}
	}
	
	unsigned long long get(int l, int r) {
		unsigned long long res = hash[r] + MOD - hash[l] * power[r - l] % MOD;
		return res - (res >= MOD ? MOD : 0);
	}

	int LCP(const RollingHash<MOD, base>& b, int l1, int r1, int l2, int r2) {
		int len = min(r1 - l1, r2 - l2);
		int low = -1, high = len + 1;
		while (high - low > 1) {
			int mid = (low + high) / 2;
			if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
			else high = mid;
		}
		return low;
	}
};

template <unsigned long long MOD, unsigned long long base1, unsigned long long base2>
vector<vector<unsigned long long> > RollingHash_2d(vector<string> &T, int r, int c) {
	vector<RollingHash<MOD, base1> > rhs;
	for (string s : T) rhs.push_back(s);
	int h = T.size(), w = T[0].size();
	vector<vector<unsigned long long> > res(h - r + 1, vector<unsigned long long>(w - c + 1));

	for (int j = 0; j + c <= w; ++j) {
		vector<unsigned long long> si(h);
		for (int i = 0; i < h; ++i) si[i] = rhs[i].get(j, j + c);
		RollingHash<MOD, base2> rh(si);
		for (int i = 0; i + r <= h; ++i)
			res[i][j] = rh.get(i, i + r);
	}
	return res;
}

int main() {
	int H, W; cin >> H >> W;
	vector<string> T(H);
	for (string& s : T) cin >> s;
	int R, C; cin >> R >> C;
	vector<string> P(R);
	for (string& s : P) cin >> s;
	const unsigned long long mod = 1000000007,
		base1 = 1007, base2 = 2009;
	auto trh = RollingHash_2d<mod, base1, base2>(T, R, C);
	auto prh = RollingHash_2d<mod, base1, base2>(P, R, C);
	for (int i = 0; i < H - R + 1; ++i)
		for (int j = 0; j < W - C + 1; ++j)
			if (trh[i][j] == prh[0][0]) printf("%d %d\n", i, j);

	return 0;
}