#include<bits/stdc++.h>
#define N 1777771
using namespace std;
typedef unsigned long long ull;
ull s[1000][1000],p[1000][1000];
ull roll[1000][1000],roll2[1000][1000];
string s1[1000],p1[1000];
int main(){
  int h,w,h1,w1;
  cin>>h>>w;

  for(int i=0;i<h;i++)cin>>s1[i];

  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)s[i][j]=s1[i][j];

  cin>>h1>>w1;
  for(int i=0;i<h1;i++)cin>>p1[i];

  for(int i=0;i<h1;i++)
    for(int j=0;j<w1;j++)p[i][j]=p1[i][j]; 



  ull a=0;
  for(int i=0;i<h1;i++)
    for(int j=0;j<w1;j++)a=a*N+p[i][j];

  for(int j=0;j<h;j++){
    ull b=0,g=1;
    for(int i=0;i<w1;i++)b*=N,b+=s[j][i],g*=N;
    roll[j][w1-1]=b;
    for(int i=w1;i<w;i++){
      b*=N,b+=s[j][i],b-=s[j][i-w1]*g;
      roll[j][i]=b;
    }
  }

  for(int j=w1-1;j<w;j++){
    ull b=0,g=1,n=1;
    for(int i=0;i<w1;i++)n*=N;
    for(int i=0;i<h1;i++)b*=n,b+=roll[i][j],g*=n;
    roll2[h1-1][j]=b;
    for(int i=h1;i<h;i++){
      b*=n,b+=roll[i][j],b-=roll[i-h1][j]*g; 
      roll2[i][j]=b;
    }
  }


  for(int i=h1-1;i<h;i++)
    for(int j=w1-1;j<w;j++)
      if(a==roll2[i][j])printf("%d %d\n",i-h1+1,j-w1+1);

    return 0;
}
### Prompt

Please create a solution in cpp 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<bits/stdc++.h>
#define N 1777771
using namespace std;
typedef unsigned long long ull;
ull s[1000][1000],p[1000][1000];
ull roll[1000][1000],roll2[1000][1000];
string s1[1000],p1[1000];
int main(){
  int h,w,h1,w1;
  cin>>h>>w;

  for(int i=0;i<h;i++)cin>>s1[i];

  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)s[i][j]=s1[i][j];

  cin>>h1>>w1;
  for(int i=0;i<h1;i++)cin>>p1[i];

  for(int i=0;i<h1;i++)
    for(int j=0;j<w1;j++)p[i][j]=p1[i][j]; 



  ull a=0;
  for(int i=0;i<h1;i++)
    for(int j=0;j<w1;j++)a=a*N+p[i][j];

  for(int j=0;j<h;j++){
    ull b=0,g=1;
    for(int i=0;i<w1;i++)b*=N,b+=s[j][i],g*=N;
    roll[j][w1-1]=b;
    for(int i=w1;i<w;i++){
      b*=N,b+=s[j][i],b-=s[j][i-w1]*g;
      roll[j][i]=b;
    }
  }

  for(int j=w1-1;j<w;j++){
    ull b=0,g=1,n=1;
    for(int i=0;i<w1;i++)n*=N;
    for(int i=0;i<h1;i++)b*=n,b+=roll[i][j],g*=n;
    roll2[h1-1][j]=b;
    for(int i=h1;i<h;i++){
      b*=n,b+=roll[i][j],b-=roll[i-h1][j]*g; 
      roll2[i][j]=b;
    }
  }


  for(int i=h1-1;i<h;i++)
    for(int j=w1-1;j<w;j++)
      if(a==roll2[i][j])printf("%d %d\n",i-h1+1,j-w1+1);

    return 0;
}
```