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 "stdio.h"
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

template <typename T>
class Mylist
{
public:
	vector<T> data;
	int R;
	int C;
	int ndim;

	//コンストラクタ
	Mylist() {};

	Mylist(int size, T init) :data(size, init), R(1), C(size) {}

	Mylist(int R_, int C_, T init) :data(R_*C_, init), R(R_), C(C_) {}

	T &at(int ri, int ci)
	{
		//if (ri < 0) ri = R + ri;
		//if (ci < 0) ci = C + ci;

		return *(data.begin() + ci + ri * C);
	}

	Mylist slice(int rs, int cs, int re, int ce)
	{
		if (rs < 0) rs = R + rs;
		if (re < 0) re = R + re;
		if (cs < 0) cs = C + cs;
		if (ce < 0) ce = C + ce;

		Mylist dist(re - rs + 1, ce - cs + 1, 0);
		for (int ri = 0; ri < dist.R; ri++) {
			for (int ci = 0; ci < dist.C; ci++) {
				dist.at(ri, ci) = this->at(rs + ri, cs + ci);
			}
		}
		return dist;
	}

	bool operator==(const Mylist &b)
	{
		return data == b.data;
	}

	bool operator!=(const Mylist &b)
	{
		return data != b.data;
	}


};

class Puzzle
{
public:

	Mylist<char> B;
	Mylist<char> P;
	bool same_flag;
	bool same_pat;

	void input()
	{
		int r, c;
		string buf;

		cin >> r >> c;
		B = Mylist<char>(r, c, '_');

		for (int ri = 0; ri < r; ri++) {
			cin >> buf;
			for (int ci = 0; ci < c; ci++) {
				B.at(ri, ci) = buf[ci];
			}
		}

		cin >> r >> c;
		P = Mylist<char>(r, c, '_');

		for (int ri = 0; ri < r; ri++) {
			cin >> buf;
			for (int ci = 0; ci < c; ci++) {
				P.at(ri, ci) = buf[ci];
			}
		}

		//same_flag = false;
		//same_pat = false;
		same_flag = is_all_same();
		same_pat = is_same_pattern();
	}

	bool is_all_same() 
	{
		char s = P.at(0,0);
		for (int ri = 0; ri < P.R; ri++) {
			for (int ci = 0; ci < P.C; ci++) {
				if (P.at(ri, ci) != s) return false;
			}
		}

		s = B.at(0, 0);
		for (int ri = 0; ri < B.R; ri++) {
			for (int ci = 0; ci < B.C; ci++) {
				if (B.at(ri, ci) != s) return false;
			}
		}
		return true;
	}

	bool is_same_pattern()
	{
		int size = 2;
		if (B.R < size || B.C < size || P.R < size || P.C < size) return false;

		Mylist<char> pat_2_2 = B.slice(0, 0, size -1 , size -1);

		for (int ri = 0; ri <= B.R - size; ri += size) {
			for (int ci = 0; ci <= B.C - size; ci += size) {
				Mylist<char> part = B.slice(ri, ci, ri + size - 1, ci + size - 1);
				if (part != pat_2_2) return false;
			}
		}

		for (int ri = 0; ri <= P.R - size; ri += size) {
			for (int ci = 0; ci <= P.C - size; ci += size) {
				Mylist<char> part = P.slice(ri, ci, ri + size - 1, ci + size - 1);
				if (part != pat_2_2) return false;
			}
		}

		return true;
	}

	void play()
	{
		if (B.R < P.R || B.C < P.C) return;

		for (int ri = 0; ri <= B.R - P.R; ri++) {
			for (int ci = 0; ci <= B.C - P.C; ci++) {

				if (same_flag || same_pat) {
					if (B.at(ri, ci) == P.at(0, 0)) {
						printf("%d %d\n", ri, ci);
					}
				}
				else {
					
					if (B.at(ri			, ci          ) != P.at( 0    , 0      )) continue;
					if (B.at(ri + P.R-1 , ci          ) != P.at(P.R -1, 0      )) continue;
					if (B.at(ri         , ci + P.C -1 ) != P.at( 0    , P.C -1 )) continue;
					if (B.at(ri + P.R-1 , ci + P.C -1 ) != P.at(P.R -1, P.C -1 )) continue;
					
					int flag = 1;
					for (int rri = 0; rri < P.R; rri++) {
						for (int cci = 0; cci < P.C; cci++) {
							if (B.at(ri + rri, ci + cci) != P.at(rri, cci)) {
							//if (B.data[(ri + rri) * B.C + ci + cci] != P.data[rri * P.C +  cci]) {
									flag = 0;
								break;
							}
						}
						if (flag == 0) break;
					}
					if (flag == 1) {
						printf("%d %d\n", ri, ci);
					}
				}
			}
		}
	}


};


int main()
{
	Puzzle puz;

	puz.input();
	puz.play();

    return 0;
}