#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vstr;

#define endl "\n"

ll power_mod(ll x, ll y, ll m){
  ll res = 1;
  if(y>0){
    res = power_mod(x,y/2,m);
    if(y%2==0) res = (res*res)%m;
    else res = (((res*res)%m)*x)%m;
  }
  return res;
}

ll trans(char c){
  return (ll)(c) + 1;
}

// r行c列の領域のハッシュ値を返す
vvvll rolling_hash2D(vstr str, ll r, ll c){
  ll h = str.size();
  ll w = str[0].size();
    if(h < r || w < c) return {}; // 空の配列を返す

  vll mod = {1000000000 + 7, 1000000000 + 9, 1000000000 + 21};
  vll base = {257, 521};

  ll mods = mod.size();

  vvvll res(h,vvll(w,vll(mods)));
  vvvll tmp(h,vvll(w,vll(mods)));

  for(ll m=0;m<mods;m++){
    ll k0 = power_mod(base[0],c,mod[m]); //行
    ll k1 = power_mod(base[1],r,mod[m]); //列

    for(ll i=0;i<h;i++){
      ll hog = 0;
      for(ll j=0;j<c;j++) hog = ( hog * base[0] % mod[m] + trans(str[i][j]) ) % mod[m];

      for(ll j=0;j+c<=w;j++){
        tmp[i][j][m] = hog;
        if(j+c < w) hog = ( hog * base[0] % mod[m] - k0 * trans(str[i][j]) + mod[m] * mod[m] + trans(str[i][j+c])) % mod[m];
      }
    }

    for(ll j=0;j+c<=w;j++){
      ll hog = 0;
      for(ll i=0;i<r;i++) hog = ( hog * base[1] % mod[m] + tmp[i][j][m]) % mod[m];

      for(ll i=0;i+r<=h;i++){
        res[i][j][m] = hog;
        if(i+r < h) hog = (hog * base[1] % mod[m] - k1 * tmp[i][j][m] + mod[m] * mod[m] + tmp[i+r][j][m]) % mod[m];
      }
    }

  }
  return res;
}
 
int main(){
    ll h, w;
    cin >> h >> w;
    vstr s(h);
    for(ll i=0;i<h;i++) cin >> s[i];
    ll r, c;
    cin >> r >> c;
    vstr t(r);
    for(ll i=0;i<r;i++) cin >> t[i];
    vvvll hs = rolling_hash2D(s,r,c);
    vvvll ht = rolling_hash2D(t,r,c);
    
    if(hs.size() == 0 || ht.size() == 0) return 0;
    
    for(ll i=0;i<h-r+1;i++){
        for(ll j=0;j<w-c+1;j++){
            if(hs[i][j] == ht[0][0]) cout << i << " " << j <<endl;
        }
    }
    
    return 0;
}

### Prompt

Please provide a Cpp coded solution 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>

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vstr;

#define endl "\n"

ll power_mod(ll x, ll y, ll m){
  ll res = 1;
  if(y>0){
    res = power_mod(x,y/2,m);
    if(y%2==0) res = (res*res)%m;
    else res = (((res*res)%m)*x)%m;
  }
  return res;
}

ll trans(char c){
  return (ll)(c) + 1;
}

// r行c列の領域のハッシュ値を返す
vvvll rolling_hash2D(vstr str, ll r, ll c){
  ll h = str.size();
  ll w = str[0].size();
    if(h < r || w < c) return {}; // 空の配列を返す

  vll mod = {1000000000 + 7, 1000000000 + 9, 1000000000 + 21};
  vll base = {257, 521};

  ll mods = mod.size();

  vvvll res(h,vvll(w,vll(mods)));
  vvvll tmp(h,vvll(w,vll(mods)));

  for(ll m=0;m<mods;m++){
    ll k0 = power_mod(base[0],c,mod[m]); //行
    ll k1 = power_mod(base[1],r,mod[m]); //列

    for(ll i=0;i<h;i++){
      ll hog = 0;
      for(ll j=0;j<c;j++) hog = ( hog * base[0] % mod[m] + trans(str[i][j]) ) % mod[m];

      for(ll j=0;j+c<=w;j++){
        tmp[i][j][m] = hog;
        if(j+c < w) hog = ( hog * base[0] % mod[m] - k0 * trans(str[i][j]) + mod[m] * mod[m] + trans(str[i][j+c])) % mod[m];
      }
    }

    for(ll j=0;j+c<=w;j++){
      ll hog = 0;
      for(ll i=0;i<r;i++) hog = ( hog * base[1] % mod[m] + tmp[i][j][m]) % mod[m];

      for(ll i=0;i+r<=h;i++){
        res[i][j][m] = hog;
        if(i+r < h) hog = (hog * base[1] % mod[m] - k1 * tmp[i][j][m] + mod[m] * mod[m] + tmp[i+r][j][m]) % mod[m];
      }
    }

  }
  return res;
}
 
int main(){
    ll h, w;
    cin >> h >> w;
    vstr s(h);
    for(ll i=0;i<h;i++) cin >> s[i];
    ll r, c;
    cin >> r >> c;
    vstr t(r);
    for(ll i=0;i<r;i++) cin >> t[i];
    vvvll hs = rolling_hash2D(s,r,c);
    vvvll ht = rolling_hash2D(t,r,c);
    
    if(hs.size() == 0 || ht.size() == 0) return 0;
    
    for(ll i=0;i<h-r+1;i++){
        for(ll j=0;j<w-c+1;j++){
            if(hs[i][j] == ht[0][0]) cout << i << " " << j <<endl;
        }
    }
    
    return 0;
}

```