#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define INF (ll)(1e18)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }


typedef unsigned long long ull;
int n, m, p, q;
const int max_size = 1000;
char field[max_size][max_size]; // でかい方
char patterns[max_size][max_size]; // 小さい方

ull hash_[max_size][max_size], tmp[max_size][max_size];

// でかい方のhash計算用だが, 小さい方にも使える
void compute_hash(char a[max_size][max_size], int n, int m) {
    const ull B1 = 9973;
    const ull B2 = 1000000007;
    
    // B1^q
    ull t1 = 1;
    rep(j, q) t1 *= B1;
    
    // 行方向
    rep(i, n) {
        ull e = 0;
        rep(j, q) e = e * B1 + a[i][j];
        for (int j = 0; j + q <= m; ++j) {
            tmp[i][j] = e;
            if (j + q < m) e = e * B1 - t1 * a[i][j] + a[i][j + q];
        }
    }
    
    // B1^p
    ull t2 = 1;
    rep(i, p) t2 *= B2;
    
    // 列方向
    for (int j = 0; j + q <= m; ++j) {
        ull e = 0;
        rep(i, p) e = e * B2 + tmp[i][j];
        
        for (int i = 0; i + p <= n; ++i) {
            hash_[i][j] = e;
            if (i + p < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + p][j];
        }
    }
}

void solve() {
    set<ull> unseen;
    
    compute_hash(patterns, p, q);
    unseen.insert(hash_[0][0]);
    // cout << hash_[0][0] << endl;
    
    compute_hash(field, n, m);
    for (int i = 0; i + p <= n; ++i) {
        for (int j = 0; j + q <= m; ++j) {
            // cout << i << " " << j << " " << hash_[i][j] << " " << n << " " << m << " " << p << " " << q << endl;
            
            if (unseen.find(hash_[i][j]) != unseen.end()) {
                cout << i << " " << j << endl;
            }
        }
    }
    
    
}

int main() {
    
    cin >> n >> m;
    rep(i, n) rep(j, m) cin >> field[i][j];
    
    cin >> p >> q;
    rep(i, p) rep(j, q) cin >> patterns[i][j];
    
    solve();
}


### Prompt

Your task is to create 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 long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define INF (ll)(1e18)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }


typedef unsigned long long ull;
int n, m, p, q;
const int max_size = 1000;
char field[max_size][max_size]; // でかい方
char patterns[max_size][max_size]; // 小さい方

ull hash_[max_size][max_size], tmp[max_size][max_size];

// でかい方のhash計算用だが, 小さい方にも使える
void compute_hash(char a[max_size][max_size], int n, int m) {
    const ull B1 = 9973;
    const ull B2 = 1000000007;
    
    // B1^q
    ull t1 = 1;
    rep(j, q) t1 *= B1;
    
    // 行方向
    rep(i, n) {
        ull e = 0;
        rep(j, q) e = e * B1 + a[i][j];
        for (int j = 0; j + q <= m; ++j) {
            tmp[i][j] = e;
            if (j + q < m) e = e * B1 - t1 * a[i][j] + a[i][j + q];
        }
    }
    
    // B1^p
    ull t2 = 1;
    rep(i, p) t2 *= B2;
    
    // 列方向
    for (int j = 0; j + q <= m; ++j) {
        ull e = 0;
        rep(i, p) e = e * B2 + tmp[i][j];
        
        for (int i = 0; i + p <= n; ++i) {
            hash_[i][j] = e;
            if (i + p < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + p][j];
        }
    }
}

void solve() {
    set<ull> unseen;
    
    compute_hash(patterns, p, q);
    unseen.insert(hash_[0][0]);
    // cout << hash_[0][0] << endl;
    
    compute_hash(field, n, m);
    for (int i = 0; i + p <= n; ++i) {
        for (int j = 0; j + q <= m; ++j) {
            // cout << i << " " << j << " " << hash_[i][j] << " " << n << " " << m << " " << p << " " << q << endl;
            
            if (unseen.find(hash_[i][j]) != unseen.end()) {
                cout << i << " " << j << endl;
            }
        }
    }
    
    
}

int main() {
    
    cin >> n >> m;
    rep(i, n) rep(j, m) cin >> field[i][j];
    
    cin >> p >> q;
    rep(i, p) rep(j, q) cin >> patterns[i][j];
    
    solve();
}


```