#include <bits/stdc++.h>
#define base 950527
#define base2 1777771
using namespace std;
typedef unsigned long long ll;
typedef pair <int,int> P;
ll A[1001][1001];
char a[1001][1001],b[1001][1001];

int main(){
  int W,H,w,h;
  cin>>H>>W;
  for(int i=0;i<H;i++)scanf("%s",a[i]);
  cin>>h>>w;
  for(int i=0;i<h;i++)scanf("%s",b[i]);

  ll target=0;
  for(int i=0;i<h;i++){
    ll key=0;
    for(int j=0;j<w;j++){
      key=key*base+b[i][j];
    }
    target=target*base2+key;
  }
  
  for(int i=0;i<H;i++){
    ll k=0,l=1;
    for(int j=0;j<W;j++){
      k=k*base+a[i][j];
      if(j-w>=0) k-= l*a[i][j-w];
      else l*=base;
      A[i][j]=k;
    }
  }

  vector <P> ans;
  for(int j=w-1;j<W;j++){
    ll k=0,l=1;
    for(int i=0;i<H;i++){
      k=k*base2+A[i][j];
      if(i-h>=0) k-=l*A[i-h][j];
      else l*=base2;
      if(target==k) ans.push_back(P(i-h+1,j-w+1)); 
    }
  }

  sort(ans.begin(),ans.end());
  for(int i=0;i<(int)ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);
  
  return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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 base 950527
#define base2 1777771
using namespace std;
typedef unsigned long long ll;
typedef pair <int,int> P;
ll A[1001][1001];
char a[1001][1001],b[1001][1001];

int main(){
  int W,H,w,h;
  cin>>H>>W;
  for(int i=0;i<H;i++)scanf("%s",a[i]);
  cin>>h>>w;
  for(int i=0;i<h;i++)scanf("%s",b[i]);

  ll target=0;
  for(int i=0;i<h;i++){
    ll key=0;
    for(int j=0;j<w;j++){
      key=key*base+b[i][j];
    }
    target=target*base2+key;
  }
  
  for(int i=0;i<H;i++){
    ll k=0,l=1;
    for(int j=0;j<W;j++){
      k=k*base+a[i][j];
      if(j-w>=0) k-= l*a[i][j-w];
      else l*=base;
      A[i][j]=k;
    }
  }

  vector <P> ans;
  for(int j=w-1;j<W;j++){
    ll k=0,l=1;
    for(int i=0;i<H;i++){
      k=k*base2+A[i][j];
      if(i-h>=0) k-=l*A[i-h][j];
      else l*=base2;
      if(target==k) ans.push_back(P(i-h+1,j-w+1)); 
    }
  }

  sort(ans.begin(),ans.end());
  for(int i=0;i<(int)ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);
  
  return 0;
}
```