#include<bits/stdc++.h>
#define N 1005
#define M1 131
#define M2 1999
using namespace std;
typedef unsigned long long ull;
int h1,w1,h2,w2;
string a[N],b[N];
ull x=1,y=1,X[N][N],Y[N][N],C[N],D=0;

int main(){
  cin>>h1>>w1;
  for(int i=0;i<h1;i++)cin>>a[i];
  cin>>h2>>w2;
  for(int i=0;i<h2;i++)cin>>b[i];
  
  for(int i=0;i<w2;i++)x*=M1;
  for(int i=0;i<h2;i++)y*=M2;
  
  for(int i=0;i<h2;i++)
    for(int j=0;j<w2;j++)
      C[i]=C[i]*M1+b[i][j];
  
  for(int i=0;i<h2;i++)D=D*M2+C[i];
  
  for(int i=0;i<h1;i++){
    X[i][0]=a[i][0];
    for(int j=1;j<w2;j++)X[i][j]=X[i][j-1]*M1+a[i][j];
    for(int j=w2;j<w1;j++)
      X[i][j]=X[i][j-1]*M1-x*a[i][j-w2]+a[i][j];
  }
  
  for(int j=w2-1;j<w1;j++){
    Y[0][j]=X[0][j];
    for(int i=1;i<h2;i++)Y[i][j]=Y[i-1][j]*M2+X[i][j];
    for(int i=h2;i<h1;i++){
      Y[i][j]=Y[i-1][j]*M2-y*X[i-h2][j]+X[i][j];
    }
  }
  for(int i=0;i<h1;i++){
    for(int j=0;j<w1;j++){
      if(Y[i][j]==D){
	printf("%d %d\n",i-h2+1  , j-w2+1);
      }
    }
  }
  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>
#define N 1005
#define M1 131
#define M2 1999
using namespace std;
typedef unsigned long long ull;
int h1,w1,h2,w2;
string a[N],b[N];
ull x=1,y=1,X[N][N],Y[N][N],C[N],D=0;

int main(){
  cin>>h1>>w1;
  for(int i=0;i<h1;i++)cin>>a[i];
  cin>>h2>>w2;
  for(int i=0;i<h2;i++)cin>>b[i];
  
  for(int i=0;i<w2;i++)x*=M1;
  for(int i=0;i<h2;i++)y*=M2;
  
  for(int i=0;i<h2;i++)
    for(int j=0;j<w2;j++)
      C[i]=C[i]*M1+b[i][j];
  
  for(int i=0;i<h2;i++)D=D*M2+C[i];
  
  for(int i=0;i<h1;i++){
    X[i][0]=a[i][0];
    for(int j=1;j<w2;j++)X[i][j]=X[i][j-1]*M1+a[i][j];
    for(int j=w2;j<w1;j++)
      X[i][j]=X[i][j-1]*M1-x*a[i][j-w2]+a[i][j];
  }
  
  for(int j=w2-1;j<w1;j++){
    Y[0][j]=X[0][j];
    for(int i=1;i<h2;i++)Y[i][j]=Y[i-1][j]*M2+X[i][j];
    for(int i=h2;i<h1;i++){
      Y[i][j]=Y[i-1][j]*M2-y*X[i-h2][j]+X[i][j];
    }
  }
  for(int i=0;i<h1;i++){
    for(int j=0;j<w1;j++){
      if(Y[i][j]==D){
	printf("%d %d\n",i-h2+1  , j-w2+1);
      }
    }
  }
  return 0;
}
```