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 <bits/stdc++.h>
using namespace std;
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1000000000 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
const ull BASE = 1e9 + 7;

struct RollingHash {

    ull base1, base2;
    ull mod1, mod2;
    vector<ull> hash1, hash2;
    vector<ull> pow1, pow2;

    RollingHash() : base1(9973), base2(1000000000 + 7), mod1(999999937), mod2(1000000000 + 7) {}

    void construct(const string &s) {
        int n = s.size();

        hash1.assign(n + 1, 0);
        hash2.assign(n + 1, 0);
        pow1.assign(n + 1, 1);
        pow2.assign(n + 1, 1);

        for (int i = 0; i < n;i++) {
            hash1[i + 1] = (hash1[i] + s[i]) * base1;
            hash2[i + 1] = (hash2[i] + s[i]) * base2;
            pow1[i + 1] = pow1[i] * base1;
            pow2[i + 1] = pow2[i] * base2;
        }
    }
    //[l, r)
    pullull get(int l, int r) {
        ull t1 = hash1[r] - hash1[l] * pow1[r - l];
        ull t2 = hash2[r] - hash2[l] * pow2[r - l];
        return make_pair(t1, t2);
    }

    bool match(int l1, int r1, int l2, int r2) {
        return get(l1, r1) == get(l2, r2) ? true : false;
    }
};

int h, w, r, c;
string t[1005], p[1005];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> h >> w;
    rep(i, h) cin >> t[i];
    cin >> r >> c;
    rep(i, r) cin >> p[i];
    if (h < r || w < c) exit(0);

    RollingHash t_yoko[1005], p_yoko[1005];
    vector<vector<ull>> t_tate(1005, vector<ull>(1005, 0));
    ull p_hs = 0;
    rep(i, h) t_yoko[i].construct(t[i]);
    rep(i, r) p_yoko[i].construct(p[i]);
    rep(i, r) p_hs = (p_hs + p_yoko[i].hash1[c]) * (1000000000 + 7);
    rep(j, w - c + 1) {
        rep(i, h) {
            pair<ull, ull> pt_hs = t_yoko[i].get(j, j + c);
            t_tate[i + 1][j] = (t_tate[i][j] + pt_hs.fi) * (1000000000 + 7);
        }
    }
    ull pw[1005];
    pw[0] = 1;
    rep2(i, 1, 1005) pw[i] = pw[i - 1] * (1000000000 + 7);
    rep(i, h - r + 1)rep(j, w - c + 1) {
        ull t_hs = t_tate[i + r][j] - t_tate[i][j] * pw[r];
        if (t_hs == p_hs) cout << i << " " << j << endl;
    }
}