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;

#define HashConst 128
#define HashMax 128456903

long long int powerdiv(long long int a, int b){
	if (b == 0) return 1;
	if (b == 1) return a;
	if (b == 2) return a*a % HashMax;
	if (b % 2 == 0) {
		long long int dum = powerdiv(a, b/2);
		return dum * dum % HashMax;
	}
	if (b % 2 != 0) {
		long long int dum = powerdiv(a, (b - 1)/2);
		return (dum * dum % HashMax) * a % HashMax;
	}
	return 0;
}

long long int modP(long long int a){
	long long int res = a % HashMax;
	if (res < 0) return res + HashMax;
	return res;
}

void RabinKarp(vector< vector<char> > T, vector< vector<char> > P, int H, int W, int R, int C){
	
	if (H < R || W < C) return;

	long long int hashconst1 = powerdiv(HashConst, R * C - C);
	long long int hashconst2 = powerdiv(HashConst, C);
	long long int hashconst3 = powerdiv(HashConst, C - 1);

	long long int P_Hash = 0;
	for (int i = 0; i < R; i++){
		for (int j = 0; j < C; j++){
			P_Hash = modP(P_Hash * HashConst + P[i][j]);
		}
	}

	long long int T_Hash_Top = 0;

	for (int i = 0; i < R; i++){
		for (int j = 0; j < C; j++){
			T_Hash_Top = modP(T_Hash_Top * HashConst + T[i][j]);
		}
	}

	long long int T_Hash = T_Hash_Top;

	for (int i = 0; i < H - R + 1; i++){
		for (int j = 0; j < W - C + 1; j++){
			long long int minusdif = 0;
			long long int plusdif = 0;
			if (j == 0){
				if (i != 0){
					for (int k = 0; k < C; k++){
						minusdif = modP(minusdif * HashConst + T[i - 1][k]);
						plusdif = modP(plusdif * HashConst + T[i + R - 1][k]);
					}
					T_Hash = modP((T_Hash_Top - modP(minusdif * hashconst1)) * hashconst2 + plusdif);
					T_Hash_Top = T_Hash;
				}
			}else{
				for (int k = 0; k < R; k++){
					minusdif = modP(minusdif * hashconst2 + T[i + k][j - 1]);
					plusdif = modP(plusdif * hashconst2 + T[i + k][j + C - 1]);
				}
				T_Hash = modP((T_Hash - modP(minusdif * hashconst3)) * HashConst + plusdif);
			}
			if (T_Hash == P_Hash) cout << i << " " << j << endl;
			//cout <<T_Hash<<endl;
		}
	}
}

int main(){
	int H, W, R, C;
	
	cin >> H >> W;
	vector< vector<char> > Field(H, vector<char>(W, 0));
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			scanf(" %c", &Field[i][j]);
		}
	}
	cin >> R >> C;
	vector< vector<char> > Pattern(R, vector<char>(C, 0));
	for (int i = 0; i < R; i++){
		for (int j = 0; j < C; j++){
			scanf(" %c", &Pattern[i][j]);
		}
	}
	
	RabinKarp(Field, Pattern, H, W, R, C);
			
	return 0;
}