#include <stdio.h>
int H, W, R, C; char s[1001][1007], t[1001][1007];
unsigned long long pw1, pw2, h1[1001][1007], h2[1001][1007], h3[1001];
int main() {
	scanf("%d%d", &H, &W);
	for(int i = 0; i < H; i++) scanf("%s", s[i]);
	scanf("%d%d", &R, &C); pw1 = 1, pw2 = 1;
	for(int i = 0; i < R; i++) scanf("%s", t[i]), pw2 *= 1000000007;
	for(int i = 0; i < C; i++) pw1 *= 257;
	for(int i = 0; i < H; i++) {
		unsigned long long w = 0;
		for(int j = 0; j < C; j++) w = w * 257 + s[i][j]; h1[i][0] = w;
		for(int j = C; j < W; j++) w = w * 257 + s[i][j] - pw1 * s[i][j - C], h1[i][j - C + 1] = w;
	}
	for(int i = 0; i <= W - C; i++) {
		unsigned long long w = 0;
		for(int j = 0; j < R; j++) w = w * 1000000007 + h1[j][i]; h2[0][i] = w;
		for(int j = R; j < H; j++) w = w * 1000000007 + h1[j][i] - pw2 * h1[j - R][i], h2[j - R + 1][i] = w;
	}
	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C; j++) h3[i] = h3[i] * 257 + t[i][j];
	}
	unsigned long long h4 = 0;
	for(int i = 0; i < R; i++) h4 = h4 * 1000000007 + h3[i];
	for(int i = 0; i <= H - R; i++) { 
		for(int j = 0; j <= W - C; j++) {
			if(h2[i][j] == h4) printf("%d %d\n", i, j);
		}
	}
}
### Prompt

In CPP, your task is to solve 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 <stdio.h>
int H, W, R, C; char s[1001][1007], t[1001][1007];
unsigned long long pw1, pw2, h1[1001][1007], h2[1001][1007], h3[1001];
int main() {
	scanf("%d%d", &H, &W);
	for(int i = 0; i < H; i++) scanf("%s", s[i]);
	scanf("%d%d", &R, &C); pw1 = 1, pw2 = 1;
	for(int i = 0; i < R; i++) scanf("%s", t[i]), pw2 *= 1000000007;
	for(int i = 0; i < C; i++) pw1 *= 257;
	for(int i = 0; i < H; i++) {
		unsigned long long w = 0;
		for(int j = 0; j < C; j++) w = w * 257 + s[i][j]; h1[i][0] = w;
		for(int j = C; j < W; j++) w = w * 257 + s[i][j] - pw1 * s[i][j - C], h1[i][j - C + 1] = w;
	}
	for(int i = 0; i <= W - C; i++) {
		unsigned long long w = 0;
		for(int j = 0; j < R; j++) w = w * 1000000007 + h1[j][i]; h2[0][i] = w;
		for(int j = R; j < H; j++) w = w * 1000000007 + h1[j][i] - pw2 * h1[j - R][i], h2[j - R + 1][i] = w;
	}
	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C; j++) h3[i] = h3[i] * 257 + t[i][j];
	}
	unsigned long long h4 = 0;
	for(int i = 0; i < R; i++) h4 = h4 * 1000000007 + h3[i];
	for(int i = 0; i <= H - R; i++) { 
		for(int j = 0; j <= W - C; j++) {
			if(h2[i][j] == h4) printf("%d %d\n", i, j);
		}
	}
}
```