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 <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <algorithm>

typedef std::pair<int, int> Coordinate;

struct State {
	int num;
	std::map<char, int> trans_to;
	// std::string str;
	int failure_to;
};

int max(int x, int y)
{
	return x>y ? x : y;
}

void constructPMA(std::vector<State>& PMA, int* finalstates, char** P, int R, int C)
{
	State starting_state;
	starting_state.num = 0;
	starting_state.failure_to = 0;
	PMA.push_back(starting_state);
	
	std::set<char> appears;
	
	// create trie tree
	for (int i=0; i<R; i++) {
		int curr_state = 0;
		for (int j=0; j<C; j++) {
			char x = P[i][j];
			appears.insert(x);
			if (PMA[curr_state].trans_to.find(x) == PMA[curr_state].trans_to.end() ) {
				State s; s.num = PMA.size();
				// s.str = pattern[i].substr(0, j+1);
				s.failure_to = 0;
				PMA.push_back(s);
				PMA[curr_state].trans_to[x] = PMA.size() - 1;
			}
			curr_state = PMA[curr_state].trans_to[x];
		}
		finalstates[i] = curr_state;
	}
	
	// failure function
	std::queue<int> que;
	que.push(0);
	
	while (!que.empty()) {
		int k = que.front(); que.pop();
		for (std::set<char>::iterator it = appears.begin(); it != appears.end(); ++it) {
			char x = *it;
			if ( PMA[k].trans_to.find(x) != PMA[k].trans_to.end() ) { // PMA[k].trans_to has a transition by x
				int next = PMA[k].trans_to[x];
				que.push(next);
				if (k > 0) {
					int f = PMA[k].failure_to;
					while (f > 0 && PMA[f].trans_to.find(x) == PMA[f].trans_to.end()) {
						f = PMA[f].failure_to;
					}
					PMA[next].failure_to = PMA[f].trans_to[x];
				}
			}
		}
	}
}

void convert(int** T, char** rectangle, std::vector<State> PMA, int H, int W)
{
	for (int i=0; i<H; i++) {
		int state_id = 0;
		for (int j=0; j<W; j++) {
			char x = rectangle[i][j];
			while ( state_id > 0 && PMA[state_id].trans_to.find(x) == PMA[state_id].trans_to.end() ) {
				state_id = PMA[state_id].failure_to;
			}
			state_id = PMA[state_id].trans_to[x];
			T[i][j] = state_id;
		}
	}
}

void constructKMP(int* KMPtable, int* P, int m)
{
	KMPtable[0] = -1;
	KMPtable[1] = 0;
	int i=2, j=0;
	while (i<m+1) {
		if (P[i-1] == P[j]) {
			KMPtable[i] = j + 1; i++; j++;
		} else if (j>0) {
			j = KMPtable[j];
		} else {
			KMPtable[i] = 0; i++;
		}
	}
	
	// std::cout << "KMP Table :" << std::endl;
	// for (int i=0; i<m+1; i++) std::cout << KMPtable[i] << std::endl;
}
	

void search(int** T, int* finalstates, int H, int W, int R, int C)
{
	std::vector<Coordinate> ans;
	
	int* KMPtable = new int[R+1];
	constructKMP(KMPtable, finalstates, R);
	
	for (int col=C-1; col<W; col++) {
		int j = 0;
		for (int row=0; row<=H-R; ) {
			if (T[row+j][col] == finalstates[j]) {
				if (j==R-1) {
					ans.push_back( Coordinate(row, col-C+1) );
					row += R - KMPtable[R];
					j = KMPtable[R];
				}
				else { j++; }
			}
			else {
				row += j - KMPtable[j];
				j = max(0, KMPtable[j]);
			}
		}
	}
	
	std::sort(ans.begin(), ans.end());
	for (int i=0; i<ans.size(); i++) {
		std::cout << ans[i].first << " " << ans[i].second << std::endl;
	}
	
	delete[] KMPtable;
}

int main()
{
	int H, W;
	std::cin >> H >> W;
	char** rectangle = new char*[H];
	for (int i=0; i<H; i++) rectangle[i] = new char[W];
	for (int i=0; i<H; i++) {
		for (int j=0; j<W; j++) std::cin >> rectangle[i][j];
	}
	
	int R, C;
	std::cin >> R >> C;
	char** pattern = new char*[R];
	for (int i=0; i<R; i++) pattern[i] = new char[C];
	for (int i=0; i<R; i++) {
		for (int j=0; j<C; j++) std::cin >> pattern[i][j];
	}
	
	std::vector<State> PMA;
	int* finalstates = new int[R];
	
	constructPMA(PMA, finalstates, pattern, R, C);
	
	int** converted_rectangle = new int*[H];
	for (int i=0; i<H; i++) converted_rectangle[i] = new int[W];
	
	convert(converted_rectangle, rectangle, PMA, H, W);
	
	/*
	
	std::cout << "Rectangle :" << std::endl;
	for (int i=0; i<H; i++) {
		for (int j=0; j<W; j++) std::cout << rectangle[i][j] << " ";
		std::cout << std::endl;
	}
	
	std::cout << "Pattern :" << std::endl;
	for (int i=0; i<R; i++) {
		for (int j=0; j<C; j++) std::cout << pattern[i][j] << " ";
		std::cout << std::endl;
	}
	
	std::cout << "PMA :" << std::endl;
	for (int i=0; i<PMA.size(); i++) {
		std::cout << i << ": ";
		for (std::map<char,int>::iterator it = PMA[i].trans_to.begin(); it != PMA[i].trans_to.end(); ++it) {
			std::cout << "[" << (*it).first << ", " << (*it).second << "], ";
		}
		
		std::cout << "failure(" << i << ") = " << PMA[i].failure_to << std::endl;
	}
	
	std::cout << "Final States :" << std::endl;
	for (int i=0; i<R; i++) {
		std::cout << finalstates[i] << std::endl;
	}
	
	std::cout << "Converted Rectangle :" << std::endl;
	for (int i=0; i<H; i++) {
		for (int j=0; j<W; j++) std::cout << converted_rectangle[i][j] << " ";
		std::cout << std::endl;
	}
	
	*/
	
	
	search(converted_rectangle, finalstates, H, W, R, C);
	
	for (int i=0; i<H; i++) delete[] converted_rectangle[i];
	delete[] converted_rectangle;
	delete[] finalstates;
	for (int i=0; i<H; i++) delete[] rectangle[i];
	delete[] rectangle;
	for (int i=0; i<R; i++) delete[] pattern[i];
	delete[] pattern;
	
	return 0;
}