/*
 * 2D string matching
 * Approach: 2D fingerprinting
 */

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ull = unsigned long long;
constexpr ull MODULUS = 1e9 + 9;
constexpr ull PRIME = 43;

int ValueOf(char ch) {
  if ('0' <= ch && ch <= '9')
    return ch - '0';
  return 10 + ch - 'a';
}

void Match(const vector<string> &T, const vector<string> &P) {
  int N = T.size(), M = T[0].size(), n = P.size(), m = P[0].size();
  // Precompute:
  // 1. h(P) -- treating rectangular ranges as 1D vectors in row-major order
  // 2. h(p^{km}) for k=1,...,n-1
  // 2a. h(p^{m-1})
  // 3. h(T[i][j..(j+m-1)]) for i=0,...,n-1, j=0,...,M-m

  ull pattern_hash = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      pattern_hash =
          (((pattern_hash * PRIME) % MODULUS) + ValueOf(P[i][j])) % MODULUS;

  ull hash_pmminus1, hash_pm;
  if (m == 1) {
    hash_pmminus1 = 1;
    hash_pm = PRIME;
  } else {
    int lgpow = 1; // current log power, minus 1
    hash_pmminus1 = PRIME;
    for (; (1 << lgpow) <= m - 1;
         ++lgpow) { // each loop, we WILL COMPUTE h(p^(2^pow))
      hash_pmminus1 = (hash_pmminus1 * hash_pmminus1) % MODULUS;
    }
    for (int to_compute = (1 << (lgpow - 1)) + 1; to_compute <= m - 1;
         ++to_compute) { // each loop, we WILL COMPUTE h(p^(to_compute))
      hash_pmminus1 = (hash_pmminus1 * PRIME) % MODULUS;
    }
    hash_pm = (hash_pmminus1 * PRIME) % MODULUS;
  }

  vector<ull> hash_ppowermtimes(n); // ith element stores h(p^{mi})
  hash_ppowermtimes[0] = 1;
  hash_ppowermtimes[1] = hash_pm;
  for (int i = 2; i < n; ++i) {
    // h(p^{mi}) = h(p^m)h(p^{m(i-1)})
    hash_ppowermtimes[i] = (hash_pm * hash_ppowermtimes[i - 1]) % MODULUS;
  }

  vector<vector<ull>> H(N, vector<ull>(M));
  for (int i = 0; i < N; ++i) {
    ull segment_hash = 0;
    for (int j = 0; j < m; ++j)
      segment_hash =
          (((segment_hash * PRIME) % MODULUS) + ValueOf(T[i][j])) % MODULUS;
    H[i][0] = segment_hash;
    for (int j = 1; j <= M - m; ++j) {
      segment_hash = (segment_hash + MODULUS -
                      ((hash_pmminus1 * ValueOf(T[i][j - 1])) % MODULUS)) %
                     MODULUS; // remove earliest element
      segment_hash = (segment_hash * PRIME) % MODULUS; // shift left
      segment_hash =
          (segment_hash + ValueOf(T[i][j + m - 1])) % MODULUS; // append
      H[i][j] = segment_hash;
    }
  }

  // Traverse and report
  vector<pair<int, int>> matches;
  for (int j = 0; j <= M - m; ++j) {
    ull text_hash = 0;
    for (int i = 0; i < n; ++i)
      text_hash = (((text_hash * hash_pm) % MODULUS) + H[i][j]) % MODULUS;
    if (text_hash == pattern_hash)
      matches.emplace_back(0, j);
    for (int i = 1; i <= N - n; ++i) {
      text_hash = (text_hash + MODULUS -
                   (((hash_ppowermtimes[n - 1]) * H[i - 1][j]) % MODULUS)) %
                  MODULUS;                                 // remove top row
      text_hash = (text_hash * hash_pm) % MODULUS;         // shift up
      text_hash = (text_hash + H[i + n - 1][j]) % MODULUS; // append
      if (text_hash == pattern_hash)
        matches.emplace_back(i, j);
    }
  }
  sort(begin(matches), end(matches));
  for (auto &p : matches)
    cout << p.first << " " << p.second << endl;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<string> T, P;
  string cur;
  while (n--) {
    cin >> cur;
    T.push_back(cur);
  }
  cin >> n >> m;
  while (n--) {
    cin >> cur;
    P.push_back(cur);
  }
  Match(T, P);
}


### Prompt

In Cpp, your task is to solve 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
/*
 * 2D string matching
 * Approach: 2D fingerprinting
 */

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ull = unsigned long long;
constexpr ull MODULUS = 1e9 + 9;
constexpr ull PRIME = 43;

int ValueOf(char ch) {
  if ('0' <= ch && ch <= '9')
    return ch - '0';
  return 10 + ch - 'a';
}

void Match(const vector<string> &T, const vector<string> &P) {
  int N = T.size(), M = T[0].size(), n = P.size(), m = P[0].size();
  // Precompute:
  // 1. h(P) -- treating rectangular ranges as 1D vectors in row-major order
  // 2. h(p^{km}) for k=1,...,n-1
  // 2a. h(p^{m-1})
  // 3. h(T[i][j..(j+m-1)]) for i=0,...,n-1, j=0,...,M-m

  ull pattern_hash = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      pattern_hash =
          (((pattern_hash * PRIME) % MODULUS) + ValueOf(P[i][j])) % MODULUS;

  ull hash_pmminus1, hash_pm;
  if (m == 1) {
    hash_pmminus1 = 1;
    hash_pm = PRIME;
  } else {
    int lgpow = 1; // current log power, minus 1
    hash_pmminus1 = PRIME;
    for (; (1 << lgpow) <= m - 1;
         ++lgpow) { // each loop, we WILL COMPUTE h(p^(2^pow))
      hash_pmminus1 = (hash_pmminus1 * hash_pmminus1) % MODULUS;
    }
    for (int to_compute = (1 << (lgpow - 1)) + 1; to_compute <= m - 1;
         ++to_compute) { // each loop, we WILL COMPUTE h(p^(to_compute))
      hash_pmminus1 = (hash_pmminus1 * PRIME) % MODULUS;
    }
    hash_pm = (hash_pmminus1 * PRIME) % MODULUS;
  }

  vector<ull> hash_ppowermtimes(n); // ith element stores h(p^{mi})
  hash_ppowermtimes[0] = 1;
  hash_ppowermtimes[1] = hash_pm;
  for (int i = 2; i < n; ++i) {
    // h(p^{mi}) = h(p^m)h(p^{m(i-1)})
    hash_ppowermtimes[i] = (hash_pm * hash_ppowermtimes[i - 1]) % MODULUS;
  }

  vector<vector<ull>> H(N, vector<ull>(M));
  for (int i = 0; i < N; ++i) {
    ull segment_hash = 0;
    for (int j = 0; j < m; ++j)
      segment_hash =
          (((segment_hash * PRIME) % MODULUS) + ValueOf(T[i][j])) % MODULUS;
    H[i][0] = segment_hash;
    for (int j = 1; j <= M - m; ++j) {
      segment_hash = (segment_hash + MODULUS -
                      ((hash_pmminus1 * ValueOf(T[i][j - 1])) % MODULUS)) %
                     MODULUS; // remove earliest element
      segment_hash = (segment_hash * PRIME) % MODULUS; // shift left
      segment_hash =
          (segment_hash + ValueOf(T[i][j + m - 1])) % MODULUS; // append
      H[i][j] = segment_hash;
    }
  }

  // Traverse and report
  vector<pair<int, int>> matches;
  for (int j = 0; j <= M - m; ++j) {
    ull text_hash = 0;
    for (int i = 0; i < n; ++i)
      text_hash = (((text_hash * hash_pm) % MODULUS) + H[i][j]) % MODULUS;
    if (text_hash == pattern_hash)
      matches.emplace_back(0, j);
    for (int i = 1; i <= N - n; ++i) {
      text_hash = (text_hash + MODULUS -
                   (((hash_ppowermtimes[n - 1]) * H[i - 1][j]) % MODULUS)) %
                  MODULUS;                                 // remove top row
      text_hash = (text_hash * hash_pm) % MODULUS;         // shift up
      text_hash = (text_hash + H[i + n - 1][j]) % MODULUS; // append
      if (text_hash == pattern_hash)
        matches.emplace_back(i, j);
    }
  }
  sort(begin(matches), end(matches));
  for (auto &p : matches)
    cout << p.first << " " << p.second << endl;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<string> T, P;
  string cur;
  while (n--) {
    cin >> cur;
    T.push_back(cur);
  }
  cin >> n >> m;
  while (n--) {
    cin >> cur;
    P.push_back(cur);
  }
  Match(T, P);
}


```