#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

const ull B1=1000000007,B2=9973;

int h,w;
char field[1111][1111];
int r,c;
char pat[1111][1111];

ull allhash[1111][1111],rowhash[1111][1111],pathash;
ull t1=1,t2=1;

int main(){
	cin.sync_with_stdio(false);
	cin>>h>>w;
	rep(i,h)cin>>field[i];
	cin>>r>>c;
	rep(i,r)cin>>pat[i];

	if(h<r||w<c)return 0;

	pathash=0;
	rep(i,r){
		ull sum=0;
		rep(j,c)sum=B1*sum+pat[i][j];
		pathash=B2*pathash+sum;
	}

	rep(i,c)t1*=B1;
	rep(i,r)t2*=B2;

	rep(i,h){
		rep(j,c)rowhash[i][0]=B1*rowhash[i][0]+field[i][j];
		repl(j,1,w-c+1){
			rowhash[i][j]=rowhash[i][j-1]*B1-t1*field[i][j-1]+field[i][j+c-1];
		}
	}

	rep(j,w){
		rep(i,r)allhash[0][j]=B2*allhash[0][j]+rowhash[i][j];
		repl(i,1,h-r+1){
			allhash[i][j]=allhash[i-1][j]*B2-t2*rowhash[i-1][j]+rowhash[i+r-1][j];
		}
	}

	rep(i,h-r+1)rep(j,w-c+1){
		if(allhash[i][j]==pathash){
			printf("%d %d\n", i,j);
		}
	}

	return 0;
}
### Prompt

In cpp, your task is to solve 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 <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

const ull B1=1000000007,B2=9973;

int h,w;
char field[1111][1111];
int r,c;
char pat[1111][1111];

ull allhash[1111][1111],rowhash[1111][1111],pathash;
ull t1=1,t2=1;

int main(){
	cin.sync_with_stdio(false);
	cin>>h>>w;
	rep(i,h)cin>>field[i];
	cin>>r>>c;
	rep(i,r)cin>>pat[i];

	if(h<r||w<c)return 0;

	pathash=0;
	rep(i,r){
		ull sum=0;
		rep(j,c)sum=B1*sum+pat[i][j];
		pathash=B2*pathash+sum;
	}

	rep(i,c)t1*=B1;
	rep(i,r)t2*=B2;

	rep(i,h){
		rep(j,c)rowhash[i][0]=B1*rowhash[i][0]+field[i][j];
		repl(j,1,w-c+1){
			rowhash[i][j]=rowhash[i][j-1]*B1-t1*field[i][j-1]+field[i][j+c-1];
		}
	}

	rep(j,w){
		rep(i,r)allhash[0][j]=B2*allhash[0][j]+rowhash[i][j];
		repl(i,1,h-r+1){
			allhash[i][j]=allhash[i-1][j]*B2-t2*rowhash[i-1][j]+rowhash[i+r-1][j];
		}
	}

	rep(i,h-r+1)rep(j,w-c+1){
		if(allhash[i][j]==pathash){
			printf("%d %d\n", i,j);
		}
	}

	return 0;
}
```