#include<bits/stdc++.h>
#define HIRA 177771
#define R 1000
using namespace std;
typedef unsigned long long ull;
ull ab[R][R],cd[R][R];
ull lo[R][R],to[R][R];
string su[R],pu[R];
int main(){
  int h1,w1,h11,w11;
  cin>>h1>>w1;
 
  for(int i=0;i<h1;i++)cin>>su[i];
 
  for(int i=0;i<h1;i++)
    for(int j=0;j<w1;j++)ab[i][j]=su[i][j];
 
  cin>>h11>>w11;
  for(int i=0;i<h11;i++)cin>>pu[i];
 
  for(int i=0;i<h11;i++)
    for(int j=0;j<w11;j++)cd[i][j]=pu[i][j]; 
 
 
 
  ull sawa=0;
  for(int i=0;i<h11;i++)
    for(int j=0;j<w11;j++)sawa=sawa*HIRA+cd[i][j];
 
  for(int j=0;j<h1;j++){
    ull bor=0,gojob=1;
    for(int i=0;i<w11;i++)bor*=HIRA,bor+=ab[j][i],gojob*=HIRA;
    lo[j][w11-1]=bor;
    for(int i=w11;i<w1;i++){
      bor*=HIRA,bor+=ab[j][i],bor-=ab[j][i-w11]*gojob;
      lo[j][i]=bor;
    }
  }
 
  for(int j=w11-1;j<w1;j++){
    ull bor=0,gojob=1,n=1;
    for(int i=0;i<w11;i++)n*=HIRA;
    for(int i=0;i<h11;i++)bor*=n,bor+=lo[i][j],gojob*=n;
    to[h11-1][j]=bor;
    for(int i=h11;i<h1;i++){
      bor*=n,bor+=lo[i][j],bor-=lo[i-h11][j]*gojob; 
      to[i][j]=bor;
    }
  }
 
 
  for(int i=h11-1;i<h1;i++)
    for(int j=w11-1;j<w1;j++)
      if(sawa==to[i][j])printf("%d %d\n",i-h11+1,j-w11+1);
 
    return 0;
}
### Prompt

Please formulate 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<bits/stdc++.h>
#define HIRA 177771
#define R 1000
using namespace std;
typedef unsigned long long ull;
ull ab[R][R],cd[R][R];
ull lo[R][R],to[R][R];
string su[R],pu[R];
int main(){
  int h1,w1,h11,w11;
  cin>>h1>>w1;
 
  for(int i=0;i<h1;i++)cin>>su[i];
 
  for(int i=0;i<h1;i++)
    for(int j=0;j<w1;j++)ab[i][j]=su[i][j];
 
  cin>>h11>>w11;
  for(int i=0;i<h11;i++)cin>>pu[i];
 
  for(int i=0;i<h11;i++)
    for(int j=0;j<w11;j++)cd[i][j]=pu[i][j]; 
 
 
 
  ull sawa=0;
  for(int i=0;i<h11;i++)
    for(int j=0;j<w11;j++)sawa=sawa*HIRA+cd[i][j];
 
  for(int j=0;j<h1;j++){
    ull bor=0,gojob=1;
    for(int i=0;i<w11;i++)bor*=HIRA,bor+=ab[j][i],gojob*=HIRA;
    lo[j][w11-1]=bor;
    for(int i=w11;i<w1;i++){
      bor*=HIRA,bor+=ab[j][i],bor-=ab[j][i-w11]*gojob;
      lo[j][i]=bor;
    }
  }
 
  for(int j=w11-1;j<w1;j++){
    ull bor=0,gojob=1,n=1;
    for(int i=0;i<w11;i++)n*=HIRA;
    for(int i=0;i<h11;i++)bor*=n,bor+=lo[i][j],gojob*=n;
    to[h11-1][j]=bor;
    for(int i=h11;i<h1;i++){
      bor*=n,bor+=lo[i][j],bor-=lo[i-h11][j]*gojob; 
      to[i][j]=bor;
    }
  }
 
 
  for(int i=h11-1;i<h1;i++)
    for(int j=w11-1;j<w1;j++)
      if(sawa==to[i][j])printf("%d %d\n",i-h11+1,j-w11+1);
 
    return 0;
}
```