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>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef unsigned long long lli;
typedef unsigned long long ull;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

int h,w;
vst m;
int r,c;
vst x;
mat cmpm;
lli hsh = 0;
lli cmp = 0;

const lli b = 1000000007;
const lli d = 1000000009;
lli bbr = 1,bbc = 1;

vector<pll> ans;

int main(){
    cin >> h >> w;
    m = vst(h);
    for(lli i = 0;i < h;i++) cin >> m[i];
    cin >> r >> c;
    x = vst(r);
    for(lli i = 0;i < r;i++) cin >> x[i];
    for(lli i = 0;i < r;i++) bbr *= d;
    for(lli i = 0;i < c;i++) bbc *= b;
    for(lli i = 0;i < r;i++){
        lli hs = 0;
        for(lli j = 0;j < c;j++){
            hs =
            hs*b + 
            x[i][j];
        }
        hsh = hsh*d + hs;
    }
    cmpm = mat(h,vll(w));
    for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
            cmpm[i][j] = 
            (j-1 >= 0 ? cmpm[i][j-1]*b : 0) + 
            m[i][j] - 
            (j-c >= 0 ? m[i][j-c]*bbc : 0);
        }
    }
    for(int j = 0;j < w;j++){
        cmp = 0;
        for(int i = 0;i < h;i++){
            cmp = 
            cmp*d + 
            cmpm[i][j] -
            (i-r >= 0 ? cmpm[i-r][j]*bbr : 0);
            if(cmp == hsh) ans.push_back(pll(i-r+1,j-c+1));
        }
    }
    sort(ans.begin(),ans.end());
    for(lli i = 0;i < ans.size();i++) cout << ans[i].first << " " << ans[i].second << endl;


    return 0;
}