#include<bits/stdc++.h>

using namespace std;
#define fordebug int hoge;cin>>hoge;
#define DEKAI 1000000007
#define INF (1<<28)
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define floot10 cout<<fixed<<setprecision(10);
//#define int long long

struct RollingHash2D{
  typedef unsigned long long ull;
 
  struct RollingHash{
	typedef unsigned long long ull;
	string S;
	ull B;
	int len;
	vector<ull> hash,p;
	RollingHash(){}
	RollingHash(string S_,ull B_=1000000007LL):
  	S(S_),B(B_),len(S.length()),hash(len+1),p(len+1){
  	hash[0]=0;p[0]=1;
  	for(int i=0;i<len;i++){
    	hash[i+1]=hash[i]*B+S[i];
    	p[i+1]=p[i]*B;
  	}
	}
	//S[l,r)
	ull find(int l,int r){
  	return hash[r]-hash[l]*p[r-l];
	}
  };
 
  vector<string> S;
  int h,w,r,c;
  ull B;
  vector<ull> p;
  vector<vector<ull> > hash;
  vector<RollingHash> rh;
  RollingHash2D(){}
  RollingHash2D(vector<string> S_,int r_,int c_,ull B_=1000000009LL):
	S(S_),h(S_.size()),w(S_[0].size()),r(r_),c(c_),B(B_),
	p(h+1),hash(h+1,vector<ull>(w-c+1,0)),rh(h){
	for(int i=0;i<h;i++) rh[i]=RollingHash(S[i]);
	p[0]=1;
	for(int i=0;i<h;i++) p[i+1]=p[i]*B;
	for(int j=0;j<w-c+1;j++){
  	hash[0][j]=0;   		 
  	for(int i=0;i<h;i++)
    	hash[i+1][j]=hash[i][j]*B+rh[i].find(j,j+c);
	}
  }
  //[i,i+r) * [j,j+c)
  ull find(int i,int j){
	return hash[i+r][j]-hash[i][j]*p[r];
  }
};


signed main(){
	int h,w;
	cin>>h>>w;
	vector<string> s;
	lp(i,h){
		string sh;
		cin>>sh;
		s.push_back(sh);
	}
	int r,c;
	cin>>r>>c;
	vector<string> t;
	lp(i,r){
		string sh;
		cin>>sh;
		t.push_back(sh);
	}
	RollingHash2D srh(s,r,c),trh(t,r,c);
	lp(i,h-r+1){
		lp(j,w-c+1){
			if(srh.find(i,j)==trh.find(0,0)){
				cout<<i<<" "<<j<<endl;
			}
		}
	}
    return 0;
}


### Prompt

Construct a cpp code solution to the problem outlined:

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 fordebug int hoge;cin>>hoge;
#define DEKAI 1000000007
#define INF (1<<28)
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define floot10 cout<<fixed<<setprecision(10);
//#define int long long

struct RollingHash2D{
  typedef unsigned long long ull;
 
  struct RollingHash{
	typedef unsigned long long ull;
	string S;
	ull B;
	int len;
	vector<ull> hash,p;
	RollingHash(){}
	RollingHash(string S_,ull B_=1000000007LL):
  	S(S_),B(B_),len(S.length()),hash(len+1),p(len+1){
  	hash[0]=0;p[0]=1;
  	for(int i=0;i<len;i++){
    	hash[i+1]=hash[i]*B+S[i];
    	p[i+1]=p[i]*B;
  	}
	}
	//S[l,r)
	ull find(int l,int r){
  	return hash[r]-hash[l]*p[r-l];
	}
  };
 
  vector<string> S;
  int h,w,r,c;
  ull B;
  vector<ull> p;
  vector<vector<ull> > hash;
  vector<RollingHash> rh;
  RollingHash2D(){}
  RollingHash2D(vector<string> S_,int r_,int c_,ull B_=1000000009LL):
	S(S_),h(S_.size()),w(S_[0].size()),r(r_),c(c_),B(B_),
	p(h+1),hash(h+1,vector<ull>(w-c+1,0)),rh(h){
	for(int i=0;i<h;i++) rh[i]=RollingHash(S[i]);
	p[0]=1;
	for(int i=0;i<h;i++) p[i+1]=p[i]*B;
	for(int j=0;j<w-c+1;j++){
  	hash[0][j]=0;   		 
  	for(int i=0;i<h;i++)
    	hash[i+1][j]=hash[i][j]*B+rh[i].find(j,j+c);
	}
  }
  //[i,i+r) * [j,j+c)
  ull find(int i,int j){
	return hash[i+r][j]-hash[i][j]*p[r];
  }
};


signed main(){
	int h,w;
	cin>>h>>w;
	vector<string> s;
	lp(i,h){
		string sh;
		cin>>sh;
		s.push_back(sh);
	}
	int r,c;
	cin>>r>>c;
	vector<string> t;
	lp(i,r){
		string sh;
		cin>>sh;
		t.push_back(sh);
	}
	RollingHash2D srh(s,r,c),trh(t,r,c);
	lp(i,h-r+1){
		lp(j,w-c+1){
			if(srh.find(i,j)==trh.find(0,0)){
				cout<<i<<" "<<j<<endl;
			}
		}
	}
    return 0;
}


```