#include<bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF 1001001001

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(int, char**)
{
  const mint B1 = 3;
  const mint B2 = 9973;

  int h, w;
  cin >> h >> w;
  vector< vector<int> > tbl(h, vector<int>(w));
  rep(i,h) {
    string s; cin >> s;
    rep(j,w) tbl[i][j] = s[j]-'0';
  }

  int r, c;
  cin >> r >> c;
  vector< vector<int> > ptn(r, vector<int>(c));
  rep(i,r) {
    string s; cin >> s;
    rep(j,c) ptn[i][j] = s[j]-'0';
  }

  vector< vector<mint> > H(h+1, vector<mint>(w+1));
  mint e1, e2;

  e2 = 1;
  rep(i,h) {
    e1 = 1;
    rep(j,w) {
      H[i+1][j+1] = e1 * e2 * (tbl[i][j]+1) + H[i][j+1] + H[i+1][j] - H[i][j];
      e1 *= B1;
    }
    e2 *= B2;
  }

  mint hash_ptn = 0;
  e2 = 1;
  rep(i,r) {
    e1 = 1;
    rep(j,c) {
      hash_ptn += e1 * e2 * (ptn[i][j]+1);
      e1 *= B1;
    }
    e2 *= B2;
  }

  vector<P> ans;
  rep(i,h-r+1) rep(j,w-c+1) {
    mint hash_tbl = H[i+r][j+c] - H[i+r][j] - H[i][j+c] + H[i][j];
    hash_tbl /= B2.pow(i) * B1.pow(j);
    if (hash_ptn.x == hash_tbl.x) {
      ans.emplace_back(i,j);
    }
  }

  for (auto a : ans) cout << a.first << " " << a.second << endl;

  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>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF 1001001001

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(int, char**)
{
  const mint B1 = 3;
  const mint B2 = 9973;

  int h, w;
  cin >> h >> w;
  vector< vector<int> > tbl(h, vector<int>(w));
  rep(i,h) {
    string s; cin >> s;
    rep(j,w) tbl[i][j] = s[j]-'0';
  }

  int r, c;
  cin >> r >> c;
  vector< vector<int> > ptn(r, vector<int>(c));
  rep(i,r) {
    string s; cin >> s;
    rep(j,c) ptn[i][j] = s[j]-'0';
  }

  vector< vector<mint> > H(h+1, vector<mint>(w+1));
  mint e1, e2;

  e2 = 1;
  rep(i,h) {
    e1 = 1;
    rep(j,w) {
      H[i+1][j+1] = e1 * e2 * (tbl[i][j]+1) + H[i][j+1] + H[i+1][j] - H[i][j];
      e1 *= B1;
    }
    e2 *= B2;
  }

  mint hash_ptn = 0;
  e2 = 1;
  rep(i,r) {
    e1 = 1;
    rep(j,c) {
      hash_ptn += e1 * e2 * (ptn[i][j]+1);
      e1 *= B1;
    }
    e2 *= B2;
  }

  vector<P> ans;
  rep(i,h-r+1) rep(j,w-c+1) {
    mint hash_tbl = H[i+r][j+c] - H[i+r][j] - H[i][j+c] + H[i][j];
    hash_tbl /= B2.pow(i) * B1.pow(j);
    if (hash_ptn.x == hash_tbl.x) {
      ans.emplace_back(i,j);
    }
  }

  for (auto a : ans) cout << a.first << " " << a.second << endl;

  return 0;
}

```