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 <cstdio>
#include <string>
#include <vector>

using namespace std;

const long long MOD=1e9+7;
const long long BASE1=0x234567, BASE2=0x3456795;

long long modpow(long long b, long long e, long long p=MOD) {
    /* Exponentiation by squaring */
    // returns n == b**e (mod p)
    long long n=1, a=b%p;
    while (e) {
        if (e & 1)
            (n *= a) %= p;

        (a *= a) %= p;
        e >>= 1;
    }
    return n;
}

long long modsub(long long a, long long b, long long p=MOD) {
    // returns n == a-b (mod p)
    return ((a-b)%p+p) % p;
}

int main() {
    size_t H, W;
    scanf("%zu %zu", &H, &W);
    vector<string> F(H);
    for (size_t i=0; i<H; ++i) {
        char buf[1<<10];
        scanf("%s", buf);
        F[i] = buf;
    }

    size_t R, C;
    scanf("%zu %zu", &R, &C);
    vector<string> G(R);
    for (size_t i=0; i<R; ++i) {
        char buf[1<<10];
        scanf("%s", buf);
        G[i] = buf;
    }

    long long target=0;
    for (size_t i=0; i<R; ++i) {
        long long key=0;
        for (size_t j=0; j<C; ++j)
            ((key *= BASE2) += G[i][j]) %= MOD;

        ((target *= BASE1) += key) %= MOD;
    }

    vector<vector<long long>> t1(H, vector<long long>(W));
    vector<vector<long long>> t2(H, vector<long long>(W));
    long long pow=modpow(BASE2, C, MOD);
    for (size_t i=0; i<H; ++i) {
        long long key=0;
        for (size_t j=0; j<W; ++j) {
            ((key *= BASE2) += F[i][j]) %= MOD;
            if (j >= C)
                key = modsub(key, F[i][j-C]*pow, MOD);

            t1[i][j] = t2[i][j] = key;
        }
    }

    pow = modpow(BASE1, R, MOD);
    for (size_t i=0; i<H; ++i)
        for (size_t j=0; j<W; ++j) {
            if (i)
                (t1[i][j] += t1[i-1][j]*BASE1) %= MOD;

            if (i >= R)
                t1[i][j] = modsub(t1[i][j], t2[i-R][j]*pow, MOD);

            if (t1[i][j]==target && i+1>=R && j+1>=C)
                printf("%zu %zu\n", i-R+1, j-C+1);
        }

    return 0;
}