#include <iostream>
#include <string>

using namespace std;

#define BASE1 124248592
#define BASE2 163282852
#define MOD 197436252

long long hash_temp[1000][1000], hash_field[1000][1000], hash_pattern[1000][1000];

void gen_hash(string str[], int H, int W, int R, int C, long long hash[][1000]) {
    for (int i = 0; i < H; i++) {
        long long temp = 0, multi = 1;
        for (int j = 0; j < W; j++) {
            temp = (temp * BASE1 + str[i][j]) % MOD;
            if (j < C) {
                multi = multi * BASE1 % MOD;
            }
            else {
                temp = ((temp - str[i][j - C] * multi) % MOD + MOD) % MOD;
            }
            hash_temp[i][j] = temp;
        }
    }
    for (int j = 0; j < W; j++) {
        long long temp = 0, multi = 1;
        for (int i = 0; i < H; i++) {
            temp = (temp * BASE2 + hash_temp[i][j]) % MOD;
            if (i < R) {
                multi = multi * BASE2 % MOD;
            }
            else {
                temp = ((temp -hash_temp[i - R][j] * multi) % MOD + MOD) % MOD;
            }
            hash[i][j] = temp;
        }
    }
}

int main() {
    int H, W, R, C;
    string field[1000], pattern[1000];

    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        cin >> field[i];
    }
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        cin >> pattern[i];
    }

    gen_hash(field, H, W, R, C, hash_field);
    gen_hash(pattern, R, C, R, C, hash_pattern);
    
    for (int i = R - 1; i < H; i++) {
        for (int j = C - 1; j < W; j++) {
            if (hash_field[i][j] == hash_pattern[R - 1][C - 1]) {
                cout << i - R + 1 << " " << j - C + 1 << "\n";
            }
        }
    }
    
    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 <iostream>
#include <string>

using namespace std;

#define BASE1 124248592
#define BASE2 163282852
#define MOD 197436252

long long hash_temp[1000][1000], hash_field[1000][1000], hash_pattern[1000][1000];

void gen_hash(string str[], int H, int W, int R, int C, long long hash[][1000]) {
    for (int i = 0; i < H; i++) {
        long long temp = 0, multi = 1;
        for (int j = 0; j < W; j++) {
            temp = (temp * BASE1 + str[i][j]) % MOD;
            if (j < C) {
                multi = multi * BASE1 % MOD;
            }
            else {
                temp = ((temp - str[i][j - C] * multi) % MOD + MOD) % MOD;
            }
            hash_temp[i][j] = temp;
        }
    }
    for (int j = 0; j < W; j++) {
        long long temp = 0, multi = 1;
        for (int i = 0; i < H; i++) {
            temp = (temp * BASE2 + hash_temp[i][j]) % MOD;
            if (i < R) {
                multi = multi * BASE2 % MOD;
            }
            else {
                temp = ((temp -hash_temp[i - R][j] * multi) % MOD + MOD) % MOD;
            }
            hash[i][j] = temp;
        }
    }
}

int main() {
    int H, W, R, C;
    string field[1000], pattern[1000];

    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        cin >> field[i];
    }
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        cin >> pattern[i];
    }

    gen_hash(field, H, W, R, C, hash_field);
    gen_hash(pattern, R, C, R, C, hash_pattern);
    
    for (int i = R - 1; i < H; i++) {
        for (int j = C - 1; j < W; j++) {
            if (hash_field[i][j] == hash_pattern[R - 1][C - 1]) {
                cout << i - R + 1 << " " << j - C + 1 << "\n";
            }
        }
    }
    
    return 0;
}
```