#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const ull P1=9973;
const ull P2=1e8+7;

int r1,r2,c1,c2;

const int N=1e3+10;
int mat[N][N],pat[N][N];
ull cal[N][N];
ull Hash;

vector<pair<int,int> > ans;

void getPatHash()
{
    Hash=0;
    for(int i=0;i<r2;i++)
    {
        ull tmp=0;
        for(int j=0;j<c2;j++)
        {
            tmp=tmp*P1+pat[i][j];
        }
        Hash=Hash*P2+tmp;
    }
}

void go()
{
    ull tmp,base;
    for(int i=0;i<r1;i++)
    {
        tmp=0;
        base=1;
        for(int j=0;j<c1&&j<c2;j++)
        {
            tmp=tmp*P1+mat[i][j];
            base=base*P1;
        }
        cal[i][0]=tmp;
        for(int j=c2;j<c1;j++)
        {
            tmp=tmp*P1-mat[i][j-c2]*base+mat[i][j];
            cal[i][j-c2+1]=tmp;
        }
    }
    for(int j=0;j+c2<=c1;j++)
    {
        tmp=0;
        base=1;
        ull temp;
        for(int i=0;i<r1&&i<r2;i++)
        {
            tmp=tmp*P2+cal[i][j];
            base=base*P2;
        }
        temp=cal[0][j];
        cal[0][j]=tmp;
        if(cal[0][j]==Hash){
            ans.push_back(make_pair(0,j));
        }
        for(int i=r2;i<r1;i++)
        {
            tmp=tmp*P2-temp*base+cal[i][j];
            temp=cal[i-r2+1][j];
            cal[i-r2+1][j]=tmp;
            if(cal[i-r2+1][j]==Hash)
            {
                ans.push_back(make_pair(i-r2+1,j));
            }
        }
    }

}

int main()
{
    scanf("%d %d",&r1,&c1);

    char ch;

    for(int i=0;i<r1;i++)
    {
        getchar();
        for(int j=0;j<c1;j++)
        {
            ch=getchar();
            mat[i][j]=ch;
        }
    }

    scanf("%d %d",&r2,&c2);

    for(int i=0;i<r2;i++)
    {
        getchar();
        for(int j=0;j<c2;j++)
        {
            ch=getchar();
            pat[i][j]=ch;
        }
    }

    getPatHash();

    go();

    sort(ans.begin(),ans.end());

    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }

    return 0;
}


### Prompt

Your challenge is to write 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 unsigned long long ull;

const ull P1=9973;
const ull P2=1e8+7;

int r1,r2,c1,c2;

const int N=1e3+10;
int mat[N][N],pat[N][N];
ull cal[N][N];
ull Hash;

vector<pair<int,int> > ans;

void getPatHash()
{
    Hash=0;
    for(int i=0;i<r2;i++)
    {
        ull tmp=0;
        for(int j=0;j<c2;j++)
        {
            tmp=tmp*P1+pat[i][j];
        }
        Hash=Hash*P2+tmp;
    }
}

void go()
{
    ull tmp,base;
    for(int i=0;i<r1;i++)
    {
        tmp=0;
        base=1;
        for(int j=0;j<c1&&j<c2;j++)
        {
            tmp=tmp*P1+mat[i][j];
            base=base*P1;
        }
        cal[i][0]=tmp;
        for(int j=c2;j<c1;j++)
        {
            tmp=tmp*P1-mat[i][j-c2]*base+mat[i][j];
            cal[i][j-c2+1]=tmp;
        }
    }
    for(int j=0;j+c2<=c1;j++)
    {
        tmp=0;
        base=1;
        ull temp;
        for(int i=0;i<r1&&i<r2;i++)
        {
            tmp=tmp*P2+cal[i][j];
            base=base*P2;
        }
        temp=cal[0][j];
        cal[0][j]=tmp;
        if(cal[0][j]==Hash){
            ans.push_back(make_pair(0,j));
        }
        for(int i=r2;i<r1;i++)
        {
            tmp=tmp*P2-temp*base+cal[i][j];
            temp=cal[i-r2+1][j];
            cal[i-r2+1][j]=tmp;
            if(cal[i-r2+1][j]==Hash)
            {
                ans.push_back(make_pair(i-r2+1,j));
            }
        }
    }

}

int main()
{
    scanf("%d %d",&r1,&c1);

    char ch;

    for(int i=0;i<r1;i++)
    {
        getchar();
        for(int j=0;j<c1;j++)
        {
            ch=getchar();
            mat[i][j]=ch;
        }
    }

    scanf("%d %d",&r2,&c2);

    for(int i=0;i<r2;i++)
    {
        getchar();
        for(int j=0;j<c2;j++)
        {
            ch=getchar();
            pat[i][j]=ch;
        }
    }

    getPatHash();

    go();

    sort(ans.begin(),ans.end());

    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }

    return 0;
}


```