#include <bits/stdc++.h>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
typedef pair<int, int> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<int> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

struct RollingHash {
    ll H, W;
    const ll B1, B2, M;
    vector<vector<ll>> h;
    vector<ll> pow1, pow2;

    RollingHash(vector<string> &str) : B1(1009), B2(1007), M(1000000009) {
        H = str.size(), W = str[0].size();
        h.assign(H + 1, vector<ll>(W + 1, 0));
        pow1.assign(H + 1, 1);
        pow2.assign(W + 1, 1);

        rep(i, H)pow1[i + 1] = pow1[i] * B1 % M;
        rep(i, W)pow2[i + 1] = pow2[i] * B2 % M;

        rep(y, H)
            rep(x, W) {
                h[y + 1][x + 1] = (h[y][x + 1] * B1 % M + h[y + 1][x] * B2 % M
                                   + (M - h[y][x] * B1 % M * B2 % M) + str[y][x]) % M;
            }
    }

    ll hash(int x1, int y1, int x2, int y2) {
        return (h[y2][x2]
                + (M - h[y1][x2] * pow1[y2 - y1] % M)
                + (M - h[y2][x1] * pow2[x2 - x1] % M)
                + (h[y1][x1] * pow1[y2 - y1] % M * pow2[x2 - x1] % M)) % M;
    }
};

int main() {

    int h, w;
    cin >> h >> w;

    vector<string> s_list(h);
    rep(i, h) cin >> s_list[i];

    int r, c;
    cin >> r >> c;
    vector<string> t_list(r);
    rep(i, r) cin >> t_list[i];

    vector<vector<vector<int>>> z(h, vector<vector<int>>(r));


    RollingHash rs(s_list), pt(t_list);
    ll target = pt.hash(0, 0, c, r);
    for (int y = r; y < h + 1; y++)
        for (int x = c; x < w + 1; x++) {
            if (rs.hash(x - c, y - r, x, y) == target) {
                cout << y - r << " " << x - c << endl;
            }
        }


}

### Prompt

Generate 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>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
typedef pair<int, int> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<int> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

struct RollingHash {
    ll H, W;
    const ll B1, B2, M;
    vector<vector<ll>> h;
    vector<ll> pow1, pow2;

    RollingHash(vector<string> &str) : B1(1009), B2(1007), M(1000000009) {
        H = str.size(), W = str[0].size();
        h.assign(H + 1, vector<ll>(W + 1, 0));
        pow1.assign(H + 1, 1);
        pow2.assign(W + 1, 1);

        rep(i, H)pow1[i + 1] = pow1[i] * B1 % M;
        rep(i, W)pow2[i + 1] = pow2[i] * B2 % M;

        rep(y, H)
            rep(x, W) {
                h[y + 1][x + 1] = (h[y][x + 1] * B1 % M + h[y + 1][x] * B2 % M
                                   + (M - h[y][x] * B1 % M * B2 % M) + str[y][x]) % M;
            }
    }

    ll hash(int x1, int y1, int x2, int y2) {
        return (h[y2][x2]
                + (M - h[y1][x2] * pow1[y2 - y1] % M)
                + (M - h[y2][x1] * pow2[x2 - x1] % M)
                + (h[y1][x1] * pow1[y2 - y1] % M * pow2[x2 - x1] % M)) % M;
    }
};

int main() {

    int h, w;
    cin >> h >> w;

    vector<string> s_list(h);
    rep(i, h) cin >> s_list[i];

    int r, c;
    cin >> r >> c;
    vector<string> t_list(r);
    rep(i, r) cin >> t_list[i];

    vector<vector<vector<int>>> z(h, vector<vector<int>>(r));


    RollingHash rs(s_list), pt(t_list);
    ll target = pt.hash(0, 0, c, r);
    for (int y = r; y < h + 1; y++)
        for (int x = c; x < w + 1; x++) {
            if (rs.hash(x - c, y - r, x, y) == target) {
                cout << y - r << " " << x - c << endl;
            }
        }


}

```