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>
using namespace std;
#include<string>
#include<stdio.h>

#define A 1355471101  // large prime number 1.
#define B 1466700101  // large prime number 2.
#define M 1522101101  // large prime number 3, larger than A and B.

int main()
{
    int i, j, H, W, R, C;
    string *T, *P;

    scanf("%d %d", &H, &W);
    T = new string [H];
    for(i = 0; i < H; i++){ cin >> T[i]; }
    scanf("%d %d", &R, &C);
    P = new string [R];
    for(i = 0; i < R; i++){ cin >> P[i]; }

    long long hash[1000][1000];
    long long s;

    for(j = 0; j < C; j++){
        s = 0;
        for(i = 0; i < R; i++){
            s = (s * A + P[i][j]) % M;
            hash[i][j] = s;
        }
    }
    for(i = 0; i < R; i++){
        s = 0;
        for(j = 0; j < C; j++){
            s = (s * B + hash[i][j]) % M;
            hash[i][j] = s;
        }
    }
    long long last_has = hash[R - 1][C - 1];

    for(j = 0; j < W; j++){
        s = 0;
        for(i = 0; i < H; i++){
            s = (s * A + T[i][j]) % M;
            hash[i][j] = s;
        }
    }
    for(i = 0; i < H; i++){
        s = 0;
        for(j = 0; j < W; j++){
            s = (s * B + hash[i][j]) % M;
            hash[i][j] = s;
        }
    }

    long long power_a, power_b, power_c, x, y, z;
    x = A, y = R, z = 1;
    for( ; y; y >>= 1){ if((y & 1) != 0){ z = (z * x) % M; } x = (x * x) % M; }
    power_a = z;
    x = B, y = C, z = 1;
    for( ; y; y >>= 1){ if((y & 1) != 0){ z = (z * x) % M; } x = (x * x) % M; }
    power_b = z;
    power_c = (power_a * power_b) % M;

    long long block1, block2, block3;
    for(i = R - 1; i < H; i++){
        for(j = C - 1; j < W; j++){
            block1 = ((i >= R ? hash[i - R][j] : 0) * power_a) % M;
            block2 = ((j >= C ? hash[i][j - C] : 0) * power_b) % M;
            block3 = M - ((((i >= R && j >= C) ? hash[i - R][j - C] : 0) * power_c) % M);
            if(hash[i][j] == (block1 + block2 + block3 + last_has) % M){
            printf("%d %d\n", i - R + 1, j - C + 1);
            }
        }
    }
    return 0;
}