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:
#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream

//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //*******************************************************************************************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILE???.
//#define INPUTFILE "input.txt" //*******************************************************************************************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scan(A) scanf("%d", &(A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl
//#define dispAll(A,n) cout << #A << " = "; rep(j, 0, (n)) {cout << setw(3) << A[j] << " ";} cout << endl

#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) (i)/2
#define l(i) (i)*2
#define r(i) (i)*2+1

int dx[] = {1,-1, 0, 0, 1, 1,-1,-1}; //???????????????????????????????¨??????????????????????????????????
int dy[] = {0, 0,-1, 1,-1, 1, 1,-1};

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long ull;

const int INF = (int)2e9+10;
const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
const ull INF_ULL = (ull)1e19-1ULL;
const int NONE = -1;
const ll MOD = (ll)1e9+7; //??§???????´???°?????£??¨??¨????????°????????????10???7??????

const int N_MAX = 1001; //num of vertex or element
const int M_MAX = 100000; //num of edge
const int DATA_MAX = 1000000010;

int N;

char T[N_MAX][N_MAX];
char P[N_MAX][N_MAX];
int H, W, R, C;

int Hash[N_MAX][N_MAX];
int Bpow[N_MAX][N_MAX];

int main() {
    
    //cin, cout????????????  ?????¨??????cin?????????????????¨??¨cin??§???scanf?????????????????¨??¨scanf??§??±?????????????????????
    cin.tie(0); //cin??¨cout??????????????????
    ios::sync_with_stdio(false); //iostream??¨stdio??????????????????
    
    //read input data
    scanf("%d %d", &H, &W);
    rep(i,0,H) {
        rep(j,0,W) {
            scanf(" %c", &T[i][j]);
        }
    }
    
    scanf("%d %d", &R, &C);
    
    rep(i,0,R) {
        rep(j,0,C) {
            scanf(" %c", &P[i][j]);
        }
    }
    
#ifdef debug
    rep(i,0,H) {
        rep(j,0,W) {
            dout << T[i][j] << " ";
        }
        dout << endl;
    }
    dout << endl;
    
    din >> R >> C;
    rep(i,0,R) {
        rep(j,0,C) {
            dout << P[i][j] << " ";
        }
        dout << endl;
    }
    dout << endl;
    
#endif
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
#endif
    //------------------------------------------------------------------------------------------
    
    
#ifdef debug
    //naive search
    bool found;
    rep(i,0,H-R+1) {
        rep(j,0,W-C+1) {
            found = true;
            rep(ii,0,R) {
                rep(jj,0,C) {
                    if(T[i+ii][j+jj]!=P[ii][jj]) {
                        found = false;
                        ii = R;
                        jj = C;
                    }
                }
            }
            
            if(found) {
                printf("%d %d\n", i, j);
            }
        }
    }
    
    
    dout << "============================================\n";
#endif
    
//    
//    //my original Rabin-Karp Algorithm (using Rolling Hash)
//    const int B = 10007;
//    int t = 1;
//    
//    for(int i=R-1; i>=0; i--) {
//        for(int j=C-1; j>=0; j--) {
//            Bpow[i][j] = t;
//            t *= B;
//        }
//    }
//    
//#ifdef debug
//    dout << "Bpow[][] = \n";
//    rep(i,0,R) {
//        rep(j,0,C) {
//            dout << Bpow[i][j] << " ";
//        }
//        dout << endl;
//    }
//#endif
//    
//    
//    int HashP = 0;
//    rep(i,0,R) {
//        rep(j,0,C) {
//            HashP += P[i][j]*Bpow[i][j];
//        }
//    }
//    
//#ifdef debug
//    disp(HashP);
//#endif
//    
//    int HashT = 0;
//    rep(i,0,R) {
//        rep(j,0,C) {
//            HashT += T[i][j]*Bpow[i][j];
//        }
//    }
//    
//#ifdef debug
//    disp(HashT);
//#endif
//    
//    //search
//    rep(i,0,H-R+1) {
//        rep(j,0,W-C+1) {
//            
//            Hash[i][j] = HashT;
//            
//#ifdef debug
//            dout << "-------------------------\n";
//            dout << i << " " << j << endl;
//            disp(HashT);
//            disp(HashP);
//            
//            dout << "Hash[][] = \n";
//            rep(i,0,H) {
//                rep(j,0,W) {
//                    dout << Hash[i][j] << " ";
//                }
//                dout << endl;
//            }
//#endif
//            
//            if(HashT == HashP) {
//                printf("%d %d\n", i, j);
//#ifdef debug
//                dout << "//////////////////////////////////////////////////////////////\n";
//#endif
//            }
//            
//            if(j+C<W) {
//                HashT *= B;
//                rep(k,i,i+R) {
//                    HashT -= T[k][j]*Bpow[k-i][0]*B;
//                    HashT += T[k][j+C]*Bpow[k-i][C-1];
//                }
//            }
//            else if(i+R<H) { //j+C = W ????????? j=W-C ???????????????j??????????????°???????????´???
//                HashT = Hash[i][0] * Bpow[R-1][0] * B;
//                rep(k,0,C) {
//                    HashT -= T[i][k]*Bpow[0][k]*Bpow[R-1][0]*B;
//                    HashT += T[i+R][k]*Bpow[R-1][k];
//                }
//            }
//            
//        }
//    }
//    
//#ifdef debug
//    dout << "============================================\n";
//#endif
    
    //orthodox procedure by Rabin-Karp Algorithm (using Rolling Hash)
    const int B1 = 10007;
    const int B2 = 100000007;
    
    
    int tmp[N_MAX][N_MAX]; //?¨??????????B1??§??????????????°???????????\?????????????????????P???T??????????????????????????\????¨??????????????¨???§???????????¨
    int hashTable_T[N_MAX][N_MAX]; //tmp?????????????????????B2??§??????????????°???????????\??????????????????????????????T[][]??????????????????????????\?????¨??????
    
    int B1powC = 1;
    rep(i,0,C) B1powC *= B1;
    
    int B2powR = 1;
    rep(i,0,R) B2powR *= B2;
    
    
    //calc. hash(P)
    int hash_P = 0;
    
    rep(i,0,R) {
        tmp[i][0] = 0;
        
        rep(jj,0,C) {
            tmp[i][0] = tmp[i][0]*B1 + P[i][jj];
        }
    }
    rep(ii,0,R) {
        hash_P = hash_P*B2 + tmp[ii][0];
    }
    
    
    
    
    //calc. tmp[][]
    rep(i,0,H) {
        tmp[i][0] = 0;
        
        rep(jj,0,C) {
            tmp[i][0] = tmp[i][0]*B1 + T[i][jj];
        }
        
        rep(j,1,W-C+1) {
            tmp[i][j] = tmp[i][j-1]*B1 - T[i][j-1]*B1powC + T[i][j+C-1];
        }
    }
    
#ifdef debug
    dout << "tmp[][] = \n";
    rep(i,0,H) {
        rep(j,0,W) {
            dout << tmp[i][j] << " ";
        }
        dout << endl;
    }
#endif
    
    
    //calc. hashTable_T
    rep(j,0,W-C+1) {
        
        hashTable_T[0][j] = 0;
        
        rep(ii,0,R) {
            hashTable_T[0][j] = hashTable_T[0][j]*B2 + tmp[ii][j];
        }
        
        rep(i,1,H-R+1) {
            hashTable_T[i][j] = hashTable_T[i-1][j]*B2 - tmp[i-1][j]*B2powR + tmp[i+R-1][j];
        }
    }
    
#ifdef debug
    disp(hash_P);
    dout << "hashTable_T[][] = \n";
    rep(i,0,H) {
        rep(j,0,W) {
            dout << hashTable_T[i][j] << " ";
        }
        dout << endl;
    }
#endif
    
    //find
    rep(i,0,H-R+1) {
        rep(j,0,W-C+1) {
            if(hash_P==hashTable_T[i][j]) {
                printf("%d %d\n", i, j);
#ifdef debug
                dout << "//////////////////////////////////////////////////////////////\n";
#endif
            }
        }
    }
    
    

    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}