#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;

const int B1=123456789;
const int B2=999999937;
const int P=1000000007;

void gen_hash(const vector<string> &m,int H,int W,int R,int C,vector<vector<long long> >&hash){
	vector<vector<long long> > hash1(H);
	hash.resize(H);

	for(int h=0;h<H;h++){
		hash1[h].resize(W);
		hash[h].resize(W);

		long long c=0;
		long long Brev=1;
		for(int w=0;w<W;w++){
			c=(c*B1+m[h][w])%P;
			if(w<C)Brev=Brev*B1%P;else c=((c-m[h][w-C]*Brev)%P+P)%P;
			hash1[h][w]=c;
		}
	}
	for(int w=0;w<W;w++){
		long long c=0;
		long long Brev=1;
			for(int h=0;h<H;h++){
			c=(c*B2+hash1[h][w])%P;
			if(h<R)Brev=Brev*B2%P;else c=((c-hash1[h-R][w]*Brev)%P+P)%P;
			hash[h][w]=c;
		}
	}
}

int main(){
	int H,W,R,C;
	cin>>H>>W;
	vector<string>field(H);
	for(int i=0;i<H;i++)cin>>field[i];
	cin>>R>>C;
	vector<string>pattern(R);
	for(int i=0;i<H;i++)cin>>pattern[i];
	vector<vector<long long> >hash_field,hash_pattern;
	gen_hash(field,H,W,R,C,hash_field);
	gen_hash(pattern,R,C,R,C,hash_pattern);
	for(int h=R-1;h<H;h++)for(int w=C-1;w<W;w++){
		if(hash_field[h][w]==hash_pattern[R-1][C-1])printf("%d %d\n",h-R+1,w-C+1);
	}
}
### Prompt

Your challenge is to write 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 <vector>
#include <cstdio>
using namespace std;

const int B1=123456789;
const int B2=999999937;
const int P=1000000007;

void gen_hash(const vector<string> &m,int H,int W,int R,int C,vector<vector<long long> >&hash){
	vector<vector<long long> > hash1(H);
	hash.resize(H);

	for(int h=0;h<H;h++){
		hash1[h].resize(W);
		hash[h].resize(W);

		long long c=0;
		long long Brev=1;
		for(int w=0;w<W;w++){
			c=(c*B1+m[h][w])%P;
			if(w<C)Brev=Brev*B1%P;else c=((c-m[h][w-C]*Brev)%P+P)%P;
			hash1[h][w]=c;
		}
	}
	for(int w=0;w<W;w++){
		long long c=0;
		long long Brev=1;
			for(int h=0;h<H;h++){
			c=(c*B2+hash1[h][w])%P;
			if(h<R)Brev=Brev*B2%P;else c=((c-hash1[h-R][w]*Brev)%P+P)%P;
			hash[h][w]=c;
		}
	}
}

int main(){
	int H,W,R,C;
	cin>>H>>W;
	vector<string>field(H);
	for(int i=0;i<H;i++)cin>>field[i];
	cin>>R>>C;
	vector<string>pattern(R);
	for(int i=0;i<H;i++)cin>>pattern[i];
	vector<vector<long long> >hash_field,hash_pattern;
	gen_hash(field,H,W,R,C,hash_field);
	gen_hash(pattern,R,C,R,C,hash_pattern);
	for(int h=R-1;h<H;h++)for(int w=C-1;w<W;w++){
		if(hash_field[h][w]==hash_pattern[R-1][C-1])printf("%d %d\n",h-R+1,w-C+1);
	}
}
```