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:
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>

using namespace std;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

typedef pair<long long int, long long int> P;

string P1[1100], P2[1100];
unsigned long long int rec[1100][1100];

int main(){
	
	int H, W;
	cin >> H >> W;
	
	for(int i = 0; i < H; i++){
		cin >> P1[i];
	}
	
	int R, C;
	cin >> R >> C;
	
	for(int i = 0; i < R; i++){
		cin >> P2[i];
	}
	
	if(H < R || W < C){
		return 0;
	}
	
	unsigned long long int B1 = 9973, B2 = 1e9 + 7, t1 = 1, t2 = 1;
	
	unsigned long long int ans = 0;
	
	for(int i = 0; i < C; i++){
		unsigned long long int val = 0;
		for(int j = 0; j < R; j++){
			val *= B1;
			val += P2[j][i];
		}
		ans *= B2;
		ans += val;
	}
	
	for(int i = 0; i < R; i++){
		t1 *= B1;
	}
	for(int i = 0; i < C; i++){
		t2 *= B2;
	}
	
	for(int i = 0; i < W; i++){
		unsigned long long int val = 0;
		for(int j = 0; j < R; j++){
			val *= B1;
			val += P1[j][i];
		}
		rec[0][i] = val;
		for(int j = R; j < H; j++){
			val *= B1;
			val += P1[j][i];
			val -= t1 * P1[j - R][i];
			rec[j - R + 1][i] = val;
		}
	}
	
	for(int i = 0; i <= H - R; i++){
		unsigned long long int val = 0;
		for(int j = 0; j < C; j++){
			val *= B2;
			val += rec[i][j];
		}
		if(val == ans){
			cout << i << " " << 0 << endl;
		}
		for(int j = C; j < W; j++){
			val *= B2;
			val += rec[i][j];
			val -= t2 * rec[i][j - C];
			if(val == ans){
				cout << i << " " << j - C + 1 << endl;
			}
		}
	}
	
	return 0;
}