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 <bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;

bool DD_Rolling_Hash(int P, int Q, const vector<vector<char>>& a, vector<vector<ull>>& res) {
	const ull B1 = 9973;
	const ull B2 = 100000007;
	if (a.size() < P || a[0].size() < Q) return false;
	vector<vector<ull>> tmp(a.size(), vector<ull>(a[0].size() - Q + 1));
	res = vector<vector<ull>>(a.size() - P + 1, vector<ull>(a[0].size() - Q + 1));

	ull t1 = 1;
	for (int j = 0; j < Q; j++) t1 *= B1;

	for (int i = 0; i < a.size(); i++) {
		ull e = 0;
		for (int j = 0; j < Q; j++) e = e * B1 + a[i][j];

		for (int j = 0; j + Q <= a[0].size(); j++) {
			tmp[i][j] = e;
			if (j + Q < a[0].size()) e = e * B1 - t1 * a[i][j] + a[i][j + Q];
		}
	}

	ull t2 = 1;
	for (int i = 0; i < P; i++) t2 *= B2;

	for (int j = 0; j + Q <= a[0].size(); j++) {
		ull e = 0;
		for (int i = 0; i < P; i++) e = e * B2 + tmp[i][j];

		for (int i = 0; i + P <= a.size(); i++) {
			res[i][j] = e;
			if (i + P < a.size()) e = e * B2 - t2 * tmp[i][j] + tmp[i + P][j];
		}
	}
	return true;
}

int main()
{
	int H, W, R, C;
	cin >> H >> W;
	vector<vector<char>> a(W, vector<char>(H));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> a[j][i];
		}
	}
	cin >> R >> C;
	vector<vector<char>> b(C, vector<char>(R));
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> b[j][i];
		}
	}
	vector<vector<ull>> res;
	DD_Rolling_Hash(C, R, b, res);
	ull f = res[0][0];

	if (DD_Rolling_Hash(C, R, a, res)) {
		for (int i = 0; i < res[0].size(); i++) {
			for (int j = 0; j < res.size(); j++) {
				if (res[j][i] == f) {
					cout << i << ' ' << j << endl;
				}
			}
		}
	}
	return 0;
}