#include<iostream>
#include<string>
#include<vector>
#include <cstdlib>
using namespace std;

typedef unsigned long long ull;

const ull X = 100001;
const ull Y = 9973;
const int MAX = 1005;

ull hash1[MAX][MAX];
ull hash2[MAX][MAX];

void hashCalc(char T[MAX][MAX],int H,int W,int R, int  C) {
	//x???X???C???
	ull x = 1;
	for (int i = 0; i < C; i++) {
		x *= X;
	}

	ull y = 1;
	for (int i = 0; i < R; i++) {
		y *= Y;
	}
	
	for (int i = 0; i < H; i++) {
		ull h = 0;
		for (int j = 0; j < C; j++) {
			h = h*X + T[i][j];
		}
		for (int k = 0; k + C <= W; k++) {
			hash1[i][k] = h;
			h = h*X + T[i][k + C] - T[i][k] * x;
		}
	}

	for (int j = 0; j + C <= W; j++) {
		ull h = 0;
		for (int i = 0; i < R; i++) {
			h=h*Y+hash1[i][j];
		}
		for (int k = 0; k + R <= H; k++) {
			hash2[k][j] = h;
			h = h*Y + hash1[k + R][j] - hash1[k][j] * y;
		}
	}
}

int main() {
	string s,t;
	
	int H, W;
	cin >> H >> W;
	char T[MAX][MAX];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> T[i][j];
		}
	}

	int R, C;
	cin >> R >> C;
	char P[R][C];
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> P[i][j];
		}
	}

	ull tmp[R];

	hashCalc(T, H, W, R, C);
	
	for (int i = 0; i < R; i++) {
		ull h = 0;
		for (int j = 0; j < C; j++) {
			h = h*X + P[i][j];
		}
		tmp[i] = h;
	}

	ull hs = 0;
	for (int i = 0; i < R; i++) {
		hs = hs*Y + tmp[i];
	}

	for (int i = 0; i + R <= H; i++) {
		for (int j = 0; j + C <= W; j++) {
			if (hash2[i][j]==hs) {
				cout << i << " " << j << endl;
			}
		}
	}
	return 0;
}
### Prompt

Create a solution in cpp for the following 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

### Response

```cpp
#include<iostream>
#include<string>
#include<vector>
#include <cstdlib>
using namespace std;

typedef unsigned long long ull;

const ull X = 100001;
const ull Y = 9973;
const int MAX = 1005;

ull hash1[MAX][MAX];
ull hash2[MAX][MAX];

void hashCalc(char T[MAX][MAX],int H,int W,int R, int  C) {
	//x???X???C???
	ull x = 1;
	for (int i = 0; i < C; i++) {
		x *= X;
	}

	ull y = 1;
	for (int i = 0; i < R; i++) {
		y *= Y;
	}
	
	for (int i = 0; i < H; i++) {
		ull h = 0;
		for (int j = 0; j < C; j++) {
			h = h*X + T[i][j];
		}
		for (int k = 0; k + C <= W; k++) {
			hash1[i][k] = h;
			h = h*X + T[i][k + C] - T[i][k] * x;
		}
	}

	for (int j = 0; j + C <= W; j++) {
		ull h = 0;
		for (int i = 0; i < R; i++) {
			h=h*Y+hash1[i][j];
		}
		for (int k = 0; k + R <= H; k++) {
			hash2[k][j] = h;
			h = h*Y + hash1[k + R][j] - hash1[k][j] * y;
		}
	}
}

int main() {
	string s,t;
	
	int H, W;
	cin >> H >> W;
	char T[MAX][MAX];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> T[i][j];
		}
	}

	int R, C;
	cin >> R >> C;
	char P[R][C];
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> P[i][j];
		}
	}

	ull tmp[R];

	hashCalc(T, H, W, R, C);
	
	for (int i = 0; i < R; i++) {
		ull h = 0;
		for (int j = 0; j < C; j++) {
			h = h*X + P[i][j];
		}
		tmp[i] = h;
	}

	ull hs = 0;
	for (int i = 0; i < R; i++) {
		hs = hs*Y + tmp[i];
	}

	for (int i = 0; i + R <= H; i++) {
		for (int j = 0; j + C <= W; j++) {
			if (hash2[i][j]==hs) {
				cout << i << " " << j << endl;
			}
		}
	}
	return 0;
}
```