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>
using namespace std;
using ull = unsigned long long;

class rolling_hash2 {
	static const ull b1 = 9973, b2 = 100000007;
	const int h, w;
	vector<ull> rh, rw;
	vector<vector<ull>> hs;
public:
	template <class T> rolling_hash2(const vector<vector<T>>& a)
		: h(a.size()), w(a[0].size()), rh(h + 1), rw(w + 1), hs(h + 1, vector<ull>(w + 1))
	{
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++)
				hs[i + 1][j + 1] = hs[i + 1][j] * b2 + a[i][j];
			for (int j = 0; j < w; j++)
				hs[i + 1][j + 1] += hs[i][j + 1] * b1;
		}
		rh[0] = rw[0] = 1;
		for (int i = 0; i < h; i++) rh[i + 1] = rh[i] * b1;
		for (int i = 0; i < w; i++) rw[i + 1] = rw[i] * b2;
	}
	ull get(int li, int lj, int ri, int rj) {
		assert(0 <= li && li <= ri && ri <= h);
		assert(0 <= lj && lj <= rj && rj <= w);
		ull u = hs[ri][rj] - hs[ri][lj] * rw[rj - lj];
		ull d = hs[li][rj] - hs[li][lj] * rw[rj - lj];
		return u - d * rh[ri - li];
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int H, W;
	cin >> H >> W;
	vector<vector<char>> A(H, vector<char>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> A[i][j];
		}
	}
	int R, C;
	cin >> R >> C;
	vector<vector<char>> B(R, vector<char>(C));
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> B[i][j];
		}
	}
	rolling_hash2 rha(A), rhb(B);
	ull h = rhb.get(0, 0, R, C);
	for (int i = 0; i + R <= H; i++) {
		for (int j = 0; j + C <= W; j++) {
			if (rha.get(i, j, i + R, j + C) == h) {
				printf("%d %d\n", i, j);
			}
		}
	}
	return 0;
}