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>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>

#define MAX 1000

using namespace std;

typedef unsigned long long ull;

int H,W,R,C;
char field[MAX][MAX]; 
char pattern[MAX][MAX]; 

ull hashh[MAX][MAX],temp[MAX][MAX];
ull target;


void compute_hash(char a[MAX][MAX], int n, int m){
	const ull B1=9973;
	const ull B2=100000007;
	
	ull t1=1;
	for(int i=0;i<C;i++) t1*=B1;
	
	for(int i=0;i<n;i++){
		ull e=0;
		for(int j=0;j<C;j++) e=e*B1+a[i][j];
		for(int j=0;C+j<=m;j++){
			temp[i][j]=e;
			e=e*B1-t1*a[i][j]+a[i][j+C];
		}
	}
	ull t2=1;
	for(int i=0;i<R;i++) t2*=B2;
	for(int j=0;j+C<=m;j++){
		ull e=0;
		for(int i=0;i<R;i++) e=e*B2+temp[i][j];
		for(int i=0;i+R<=n;i++){
			hashh[i][j]=e;
			e=e*B2-t2*temp[i][j]+temp[i+R][j];
		}
	}
}

void solve(){
	compute_hash(pattern,R,C);
	target=hashh[0][0];
	compute_hash(field,H,W);
	
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(target==hashh[i][j])
			printf("%d %d\n",i,j);
		}
	}
}

int main(){
	scanf("%d %d",&H,&W);
	cin.ignore();
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			scanf("%c",&field[i][j]);
		}
		cin.ignore();
	}
	scanf("%d %d",&R,&C);
	cin.ignore();
	for(int i=0;i<R;i++){
		for(int j=0;j<C;j++){
			scanf("%c",&pattern[i][j]);
		}
		cin.ignore();
	}
	if(H>=R&&W>=C)
	solve();
}