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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
long Pow(long X,long R){
	long Z = X;
	long ans = 1;
	while(R){
		if(R % 2){
			ans *= Z;
			ans %= mod;
		}
		Z = Z*Z%mod;
		R /= 2;
	}
	return ans;
}
long Rev(long X){
	return Pow(X,mod-2);
}
struct HashNumber{
	static const long X0 = 118306800;
	static const long X1 = 686550364;
	static const long X2 = 218792700;
	static const long X3 = 202607072;
	static const long reX0 = 346452252;
	static const long reX1 = 153603143;
	static const long reX2 = 60932367;
	static const long reX3 = 30668905;
	long val0;
	long val1;
	long val2;
	long val3;
	HashNumber(long v0,long v1,long v2,long v3){
		val0 = v0;
		val1 = v1;
		val2 = v2;
		val3 = v3;
	}
	HashNumber(long v){
		val0 = v;
		val1 = v;
		val2 = v;
		val3 = v;
	}
	HashNumber(){
		val0 = 0;
		val1 = 0;
		val2 = 0;
		val3 = 0;
	}
	static HashNumber make(long v0,long v1,long v2,long v3){
		HashNumber ans(v0,v1,v2,v3);
		return ans;
	}
	HashNumber& operator=(const HashNumber &x){
		val0 = x.val0;
		val1 = x.val1;
		val2 = x.val2;
		val3 = x.val3;
		return *this;
	}
	HashNumber operator+(const long &x){
		return make((val0+x)%mod,(val1+x)%mod,(val2+x)%mod,(val3+x)%mod);
	}
	HashNumber operator-(const long &x){
		return make((val0-x+mod)%mod,(val1-x+mod)%mod,(val2-x+mod)%mod,(val3-x+mod)%mod);
	}
	HashNumber operator+(const HashNumber &x){
		return make((val0+x.val0)%mod,(val1+x.val1)%mod,(val2+x.val2)%mod,(val3+x.val3)%mod);
	}
	HashNumber operator-(const HashNumber &x){
		return make((val0-x.val0+mod)%mod,(val1-x.val1+mod)%mod,(val2-x.val2+mod)%mod,(val3-x.val3+mod)%mod);
	}
	HashNumber operator<<(const long &x){
		return make(val0*Pow(X0,x)%mod,val1*Pow(X1,x)%mod,val2*Pow(X2,x)%mod,val3*Pow(X3,x)%mod);
	}
	HashNumber operator>>(const long &x){
		return make(val0*Pow(reX0,x)%mod,val1*Pow(reX1,x)%mod,val2*Pow(reX2,x)%mod,val3*Pow(reX3,x)%mod);
	}
	bool operator==(const HashNumber &x){
		return val0==x.val0 && val1==x.val1 && val2==x.val2 && val3==x.val3;
	}
	bool operator!=(const HashNumber &x){
		return val0!=x.val0 || val1!=x.val1 || val2!=x.val2 || val3!=x.val3;
	}
	bool operator<(const HashNumber &x){
		if(val0 != x.val0){
			return val0 < x.val0;
		}
		if(val1 != x.val1){
			return val1 < x.val1;
		}
		if(val2 != x.val2){
			return val2 < x.val2;
		}
		return val3 < x.val3;
	}
	bool operator>(const HashNumber &x){
		if(val0 != x.val0){
			return val0 > x.val0;
		}
		if(val1 != x.val1){
			return val1 > x.val1;
		}
		if(val2 != x.val2){
			return val2 > x.val2;
		}
		return val3 > x.val3;
	}
	bool operator<=(const HashNumber &x){
		if(val0 != x.val0){
			return val0 < x.val0;
		}
		if(val1 != x.val1){
			return val1 < x.val1;
		}
		if(val2 != x.val2){
			return val2 < x.val2;
		}
		return val3 <= x.val3;
	}
	bool operator>=(const HashNumber &x){
		if(val0 != x.val0){
			return val0 > x.val0;
		}
		if(val1 != x.val1){
			return val1 > x.val1;
		}
		if(val2 != x.val2){
			return val2 > x.val2;
		}
		return val3 >= x.val3;
	}
	HashNumber& operator+=(const long &x){
		return *this = (*this+x);
	}
	HashNumber operator-=(const long &x){
		return *this = (*this-x);
	}
	HashNumber& operator+=(const HashNumber &x){
		return *this = (*this+x);
	}
	HashNumber operator-=(const HashNumber &x){
		return *this = (*this-x);
	}
	HashNumber& operator<<=(const long &x){
		return *this = (*this<<x);
	}
	HashNumber operator>>=(const long &x){
		return *this = (*this>>x);
	}
};
int chartoint(char x){
	if('0' <= x && x <= '9'){
		return x - '0';
	}
	if('a' <= x && x <= 'z'){
		return x - 'a' + 10;
	}
	return x - 'A' + 36;
}
HashNumber DP[1000][1000];
void Calc(){
	int H = rei();
	int W = rei();
	for(int i=0;i<H;i++){
		string S = res();
		for(int j=0;j<W;j++){
			HashNumber d;
			d += chartoint(S[j]);
			d <<= (1000*i+j);
			if(i != 0){
				d += DP[i-1][j];
			}
			if(j != 0){
				d += DP[i][j-1];
			}
			if(i != 0 && j != 0){
				d -= DP[i-1][j-1];
			}
			DP[i][j] = d;
		}
	}
	HashNumber target;
	int h = rei();
	int w = rei();
	for(int i=0;i<h;i++){
		string S = res();
		for(int j=0;j<w;j++){
			HashNumber d;
			d += chartoint(S[j]);
			d <<= (1000*i+j);
			target += d;
		}
	}
	for(int i=h-1;i<H;i++){
		for(int j=w-1;j<W;j++){
			HashNumber d = DP[i][j];
			if(i != h-1){
				d -= DP[i-h][j];
			}
			if(j != w-1){
				d -= DP[i][j-w];
			}
			if(i != h-1 && j != w-1){
				d += DP[i-h][j-w];
			}
			d >>= (1000*(i-h+1)+(j-w+1));
			if(target == d){
				cout << i-h+1 << " " << j-w+1 << endl;
			}
		}
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}