#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ll = long long;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;

template<class T, class S>
bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S>
bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}


/*
#include <string>
#include <unordered_set>
#include <vector>
#include <utility>
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
using ull = unsigned long long;
using VS = vector<string>;
using Pi_i = pair<int, int>;
*/

//一致する全ての部分の左端のインデックス
class RollingHush2DIndex{
    VS field, purpose;
    const ull B1 = 9973;
    const ull B2 = 100000007;
public:
    RollingHush2DIndex(){}
    RollingHush2DIndex(VS T, VS P): field(T), purpose(P){}
private:
    ull sthash(VS s){
        int R = purpose.size(), C = purpose[0].length();
        vector<ull> tmp(R, 0ull);
        //行方向
        ull b1p = 1;
        REP(i, R){
            REP(j, C){
                tmp[i] = tmp[i] * B1 + s[i][j];
            }
        }
        ull b2p = 1;
        ull hashed = 0;
        REP(i, R){
            b2p *= B2;
            hashed = hashed * B2 + tmp[i];
        }
        return hashed;
    }
public:
    void setPurpose(VS s){
        purpose = s;
    }
    void setField(VS s){
        field = s;
    }

    vector<Pi_i> getCommonIdx(){
        vector<Pi_i> ret;
        int H = field.size(), W = field[0].length();
        int R = purpose.size(), C = purpose[0].length();
        if(H < R || W < C) return ret;
        ull b1p = 1, b2p = 1;
        REP(i, C) b1p *= B1;
        REP(i, R) b2p *= B2;
        ull fh = sthash(field), ph = sthash(purpose);
        ull prvRowLeft = fh;
        REPS(i, H-R){
            if(i){
                fh = prvRowLeft*B2;
                ull p1 = 1;
                RREP(j, C-1){
                    fh += (-field[i-1][j] * b2p + field[i+R-1][j]) * p1;
                    p1 *= B1;
                }
                prvRowLeft = fh;
            }
            REPS(j, W-C){
                if(j){
                    ull p2 = 1;
                    fh *= B1;
                    RREP(k, R-1){
                        fh += (-field[i+k][j-1]*b1p + field[i+k][j+C-1]) * p2;
                        p2 *= B2;
                    }
                }
                //    cout << i << " " << j << ": " << sh << "\n";
                if(fh == ph) ret.PB(MP(i, j));
            }

        }
        return ret;
    }
};


int main(){
    int H, W, R, C;
    cin >> H >> W;
    VS field(H);
    REP(i, H) cin >> field[i];
    cin >> R >> C;
    VS pattern(R);
    REP(i, R) cin >> pattern[i];
    RollingHush2DIndex RH(field, pattern);
    vector<Pi_i> ans = RH.getCommonIdx();
    REP(i, ans.size())
        cout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}


### Prompt

Create a solution in cpp for 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
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ll = long long;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;

template<class T, class S>
bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S>
bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}


/*
#include <string>
#include <unordered_set>
#include <vector>
#include <utility>
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
using ull = unsigned long long;
using VS = vector<string>;
using Pi_i = pair<int, int>;
*/

//一致する全ての部分の左端のインデックス
class RollingHush2DIndex{
    VS field, purpose;
    const ull B1 = 9973;
    const ull B2 = 100000007;
public:
    RollingHush2DIndex(){}
    RollingHush2DIndex(VS T, VS P): field(T), purpose(P){}
private:
    ull sthash(VS s){
        int R = purpose.size(), C = purpose[0].length();
        vector<ull> tmp(R, 0ull);
        //行方向
        ull b1p = 1;
        REP(i, R){
            REP(j, C){
                tmp[i] = tmp[i] * B1 + s[i][j];
            }
        }
        ull b2p = 1;
        ull hashed = 0;
        REP(i, R){
            b2p *= B2;
            hashed = hashed * B2 + tmp[i];
        }
        return hashed;
    }
public:
    void setPurpose(VS s){
        purpose = s;
    }
    void setField(VS s){
        field = s;
    }

    vector<Pi_i> getCommonIdx(){
        vector<Pi_i> ret;
        int H = field.size(), W = field[0].length();
        int R = purpose.size(), C = purpose[0].length();
        if(H < R || W < C) return ret;
        ull b1p = 1, b2p = 1;
        REP(i, C) b1p *= B1;
        REP(i, R) b2p *= B2;
        ull fh = sthash(field), ph = sthash(purpose);
        ull prvRowLeft = fh;
        REPS(i, H-R){
            if(i){
                fh = prvRowLeft*B2;
                ull p1 = 1;
                RREP(j, C-1){
                    fh += (-field[i-1][j] * b2p + field[i+R-1][j]) * p1;
                    p1 *= B1;
                }
                prvRowLeft = fh;
            }
            REPS(j, W-C){
                if(j){
                    ull p2 = 1;
                    fh *= B1;
                    RREP(k, R-1){
                        fh += (-field[i+k][j-1]*b1p + field[i+k][j+C-1]) * p2;
                        p2 *= B2;
                    }
                }
                //    cout << i << " " << j << ": " << sh << "\n";
                if(fh == ph) ret.PB(MP(i, j));
            }

        }
        return ret;
    }
};


int main(){
    int H, W, R, C;
    cin >> H >> W;
    VS field(H);
    REP(i, H) cin >> field[i];
    cin >> R >> C;
    VS pattern(R);
    REP(i, R) cin >> pattern[i];
    RollingHush2DIndex RH(field, pattern);
    vector<Pi_i> ans = RH.getCommonIdx();
    REP(i, ans.size())
        cout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}


```