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

Solution (in CPP):

Solution:
#include <iostream>

#define B (1000000007ULL)
using namespace std;
typedef unsigned long long ull;

int h, w, r, c;
char t[1000][1001], p[1000][1001];
ull th[1000][1000], ph[1000];
int st[1001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>h>>w;
    cin.ignore();
    for(int i=0; i<h; i++) 
        cin.getline(t[i], 1001);
    cin>>r>>c;
    cin.ignore();
    for(int i=0; i<r; i++) 
        cin.getline(p[i], 1001);

    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            ph[i]=ph[i]*B+p[i][j];
        }
    }
    ull bn=B;
    for(int i=1; i<c; i++) bn*=B;
    for(int i=0; i<h; i++){
        for(int j=0; j<c; j++) th[i][0]=th[i][0]*B+t[i][j];
        for(int j=0; j<w-c; j++) th[i][j+1]=th[i][j]*B-t[i][j]*bn+t[i][j+c];
    }
    for(int y=0; y<=h-r; y++){
        for(int x=0; x<=w-c; x++){
            int i;
            for(i=0; i<r&&th[y+i][x]==ph[i]; i++);
            if(i==r) cout<<y<<' '<<x<<'\n';
        }
    }
    return 0;
}