#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int MAX_N = 1001;
const ull B1 = 9973;
const ull B2 = 1e9 + 7;
int H, W, P, Q;
ull Hash[MAX_N][MAX_N], tmp[MAX_N][MAX_N];
char field[MAX_N][MAX_N], patterns[MAX_N][MAX_N];
void RollingHash(int n, int m, char ch[MAX_N][MAX_N])
{
    //行方向
    ull t1 = 1;
    for(int j = 0; j < Q; j++) t1 *= B1;
    for(int i = 0; i < n; i++)
    {
        ull e1 = 0;
        for(int j = 0; j < Q; j++) e1 = e1 * B1 + ch[i][j];
        for(int j = 0; j + Q <= m; j++)
        {
            tmp[i][j] = e1;
            if(j + Q < m) e1 = e1 * B1 - t1 * ch[i][j] + ch[i][j + Q];
        }
    }
    //双方向
    ull t2 = 1;
    for(int i = 0; i < P; i++) t2 *= B2;
    for(int j = 0; j + Q <= m; j++)
    {
        ull e2 = 0;
        for(int i = 0; i < P; i++) e2 = e2 * B2 + tmp[i][j];
        for(int i = 0; i + P <= n; i++)
        {
            Hash[i][j] = e2;
            if(i + P < n) e2 = e2 * B2 - t2 * tmp[i][j] + tmp[i + P][j];
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    for(int i = 0; i < H; i++)
    {
        for(int j = 0; j < W; j++)
        {
            cin >> field[i][j];
        }
    }
    cin >> P >> Q;
    for(int i = 0; i < P; i++)
    {
        for(int j = 0; j < Q; j++)
        {
            cin >> patterns[i][j];
        }
    }
    RollingHash(P, Q, patterns);
    ull f = Hash[0][0];
    RollingHash(H, W, field);
    for(int i = 0; i + P <= H; i++)
    {
        for(int j = 0; j + Q <= W; j++)
        {
            //cout << Hash[i][j] << " " << f << endl;
            if(Hash[i][j] == f) cout << i << " " << j << "\n";
        }
    }
    return 0;
}

### Prompt

Please create a solution in cpp 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>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int MAX_N = 1001;
const ull B1 = 9973;
const ull B2 = 1e9 + 7;
int H, W, P, Q;
ull Hash[MAX_N][MAX_N], tmp[MAX_N][MAX_N];
char field[MAX_N][MAX_N], patterns[MAX_N][MAX_N];
void RollingHash(int n, int m, char ch[MAX_N][MAX_N])
{
    //行方向
    ull t1 = 1;
    for(int j = 0; j < Q; j++) t1 *= B1;
    for(int i = 0; i < n; i++)
    {
        ull e1 = 0;
        for(int j = 0; j < Q; j++) e1 = e1 * B1 + ch[i][j];
        for(int j = 0; j + Q <= m; j++)
        {
            tmp[i][j] = e1;
            if(j + Q < m) e1 = e1 * B1 - t1 * ch[i][j] + ch[i][j + Q];
        }
    }
    //双方向
    ull t2 = 1;
    for(int i = 0; i < P; i++) t2 *= B2;
    for(int j = 0; j + Q <= m; j++)
    {
        ull e2 = 0;
        for(int i = 0; i < P; i++) e2 = e2 * B2 + tmp[i][j];
        for(int i = 0; i + P <= n; i++)
        {
            Hash[i][j] = e2;
            if(i + P < n) e2 = e2 * B2 - t2 * tmp[i][j] + tmp[i + P][j];
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    for(int i = 0; i < H; i++)
    {
        for(int j = 0; j < W; j++)
        {
            cin >> field[i][j];
        }
    }
    cin >> P >> Q;
    for(int i = 0; i < P; i++)
    {
        for(int j = 0; j < Q; j++)
        {
            cin >> patterns[i][j];
        }
    }
    RollingHash(P, Q, patterns);
    ull f = Hash[0][0];
    RollingHash(H, W, field);
    for(int i = 0; i + P <= H; i++)
    {
        for(int j = 0; j + Q <= W; j++)
        {
            //cout << Hash[i][j] << " " << f << endl;
            if(Hash[i][j] == f) cout << i << " " << j << "\n";
        }
    }
    return 0;
}

```