#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;

const ull B1 = (ull)1e9 + 7;
const ull B2 = (ull)1e9 + 9;
int H, W, R, C;
vector<string> s, p;
vector< vector<ull> > HASH[2];

vector< vector<ull> > compute_hash(vector<string> &s, int h, int w, int r, int c) {
  vector< vector<ull> > res(h, vector<ull>(w, 0)), tmp = res;
  ull t1 = 1, t2 = 1;
  for (int i = 0; i < c; i++) t1 *= B1;
  for (int i = 0; i < h; i++) {
    ull e = 0;
    for (int j = 0; j < c; j++) e = e * B1 + s[i][j];
    for (int j = 0; j + c <= w; j++) {
      tmp[i][j] = e;
      if (j + c >= w) continue;
      e = e * B1 + s[i][j + c] - s[i][j] * t1;
    }
  }
  for (int i = 0; i < r; i++) t2 *= B2;
  for (int j = 0; j < w; j++) {
    ull e = 0;
    for (int i = 0; i < r; i++) e = e * B2 + tmp[i][j];
    for (int i = 0; i + r <= h; i++) {
      res[i][j] = e;
      if (i + r >= h) continue;
      e = e * B2 + tmp[i + r][j] - tmp[i][j] * t2;
    }
  }
  return res;
}

int main(void) {
  cin >> H >> W;
  s.resize(H);
  for (int i = 0; i < H; i++) {
    cin >> s[i];
  }
  cin >> R >> C;
  p.resize(R);
  for (int i = 0; i < R; i++) {
    cin >> p[i];
  }

  if (R <= H && C <= W) {
    HASH[0] = compute_hash(s, H, W, R, C);
    HASH[1] = compute_hash(p, R, C, R, C);
    
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (HASH[0][i][j] != HASH[1][0][0]) continue;
        cout << i << " " << j << 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;
typedef unsigned long long ull;

const ull B1 = (ull)1e9 + 7;
const ull B2 = (ull)1e9 + 9;
int H, W, R, C;
vector<string> s, p;
vector< vector<ull> > HASH[2];

vector< vector<ull> > compute_hash(vector<string> &s, int h, int w, int r, int c) {
  vector< vector<ull> > res(h, vector<ull>(w, 0)), tmp = res;
  ull t1 = 1, t2 = 1;
  for (int i = 0; i < c; i++) t1 *= B1;
  for (int i = 0; i < h; i++) {
    ull e = 0;
    for (int j = 0; j < c; j++) e = e * B1 + s[i][j];
    for (int j = 0; j + c <= w; j++) {
      tmp[i][j] = e;
      if (j + c >= w) continue;
      e = e * B1 + s[i][j + c] - s[i][j] * t1;
    }
  }
  for (int i = 0; i < r; i++) t2 *= B2;
  for (int j = 0; j < w; j++) {
    ull e = 0;
    for (int i = 0; i < r; i++) e = e * B2 + tmp[i][j];
    for (int i = 0; i + r <= h; i++) {
      res[i][j] = e;
      if (i + r >= h) continue;
      e = e * B2 + tmp[i + r][j] - tmp[i][j] * t2;
    }
  }
  return res;
}

int main(void) {
  cin >> H >> W;
  s.resize(H);
  for (int i = 0; i < H; i++) {
    cin >> s[i];
  }
  cin >> R >> C;
  p.resize(R);
  for (int i = 0; i < R; i++) {
    cin >> p[i];
  }

  if (R <= H && C <= W) {
    HASH[0] = compute_hash(s, H, W, R, C);
    HASH[1] = compute_hash(p, R, C, R, C);
    
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (HASH[0][i][j] != HASH[1][0][0]) continue;
        cout << i << " " << j << endl;
      }
    }
  }

  return 0;
}

```