#include<iostream>
#include<string>
#include<cstring>
using namespace std;

typedef unsigned long long ull;

#define MAX 2100

#define  B  (ull)((int)1e9+7)
#define  B2  (ull)((int)1e9+9)

int H, W, R, C;
string hw[MAX], rc[MAX];

void solve(){
	ull bm = 1, bm2 = 1, hhw = 0, hrc = 0, temph[MAX] = {}, temp = 0;
	
	for(int i = 0; i < C; i++) bm *= B;
	for(int i = 0; i < R; i++) bm2 *= B2;
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++) temph[i] = temph[i]*B + hw[i][j];
		hhw = hhw*B2 + temph[i];
		// for(int j = C; j < W; j++) temp = temp*B + hw[i][j];
	}
	
	for(int i = 0; i < R; i++){
		temp = 0;
		for(int j = 0; j < C; j++) temp = temp*B + rc[i][j];
		hrc = hrc*B2 + temp;
	}
	// cout<<hhw<<" "<<hrc<<endl;
	for(int i = 0; i + R <= H; i++){
		for(int j = 0; j + C <= W; j++){
			// cout<<i<<" "<<j<<" "<<hhw<<" "<<hrc<<endl;
			if(hhw == hrc) cout<<i<<" "<<j<<endl;
			if(j+C>W)continue;
			hhw = 0;
			for(int k = 0; k < R; k++){
				temph[i+k] = temph[i+k]*B + hw[i+k][j+C] - hw[i+k][j]*bm;
				// temph[i+k] = 0;
				// for(int l = j; l < C+j; l++) temph[i+k] = temph[i+k]*B + hw[i+k][j];
				hhw = hhw*B2 + temph[i+k];
				// cout<<i<<" "<<j<<" "<<k<<" "<<temph[i+k]<<endl;
			}
			// cout<<hhw<<" +++ "<<endl<<endl;
		}
		if(i+R>H)continue;
		hhw = 0;
		for(int j = 1; j <= R; j++){
			temph[i+j] = 0;
			for(int k = 0; k < C; k++) temph[i+j] = temph[i+j]*B + hw[i+j][k];
			hhw = hhw*B2 + temph[i+j];
		}
		// for(int j = 0; j < C; j++) temph[i+R] = temph[i+R]*B + hw[i+R][j];
		// hhw = hhw*B2 + temph[i+R] - temph[i]*bm2;		
	}
}

int main(){
	cin>>H>>W;
	
	for(int i = 0; i < H; i++){
		cin>>hw[i];
	}
	
	cin>>R>>C;
	
	for(int i = 0; i < R; i++){
		cin>>rc[i];
	}
	
	solve();
	
	return 0;
}

### Prompt

Your task is to create a Cpp solution to the following 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

### Response

```cpp
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

typedef unsigned long long ull;

#define MAX 2100

#define  B  (ull)((int)1e9+7)
#define  B2  (ull)((int)1e9+9)

int H, W, R, C;
string hw[MAX], rc[MAX];

void solve(){
	ull bm = 1, bm2 = 1, hhw = 0, hrc = 0, temph[MAX] = {}, temp = 0;
	
	for(int i = 0; i < C; i++) bm *= B;
	for(int i = 0; i < R; i++) bm2 *= B2;
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++) temph[i] = temph[i]*B + hw[i][j];
		hhw = hhw*B2 + temph[i];
		// for(int j = C; j < W; j++) temp = temp*B + hw[i][j];
	}
	
	for(int i = 0; i < R; i++){
		temp = 0;
		for(int j = 0; j < C; j++) temp = temp*B + rc[i][j];
		hrc = hrc*B2 + temp;
	}
	// cout<<hhw<<" "<<hrc<<endl;
	for(int i = 0; i + R <= H; i++){
		for(int j = 0; j + C <= W; j++){
			// cout<<i<<" "<<j<<" "<<hhw<<" "<<hrc<<endl;
			if(hhw == hrc) cout<<i<<" "<<j<<endl;
			if(j+C>W)continue;
			hhw = 0;
			for(int k = 0; k < R; k++){
				temph[i+k] = temph[i+k]*B + hw[i+k][j+C] - hw[i+k][j]*bm;
				// temph[i+k] = 0;
				// for(int l = j; l < C+j; l++) temph[i+k] = temph[i+k]*B + hw[i+k][j];
				hhw = hhw*B2 + temph[i+k];
				// cout<<i<<" "<<j<<" "<<k<<" "<<temph[i+k]<<endl;
			}
			// cout<<hhw<<" +++ "<<endl<<endl;
		}
		if(i+R>H)continue;
		hhw = 0;
		for(int j = 1; j <= R; j++){
			temph[i+j] = 0;
			for(int k = 0; k < C; k++) temph[i+j] = temph[i+j]*B + hw[i+j][k];
			hhw = hhw*B2 + temph[i+j];
		}
		// for(int j = 0; j < C; j++) temph[i+R] = temph[i+R]*B + hw[i+R][j];
		// hhw = hhw*B2 + temph[i+R] - temph[i]*bm2;		
	}
}

int main(){
	cin>>H>>W;
	
	for(int i = 0; i < H; i++){
		cin>>hw[i];
	}
	
	cin>>R>>C;
	
	for(int i = 0; i < R; i++){
		cin>>rc[i];
	}
	
	solve();
	
	return 0;
}

```