I. Image Matching
time limit per test
4 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

It's Cody's birthday! This year, instead of giving him a long string or an integer array with special properties, his friends surprised him with an interesting picture. Cody suspects that the image was cropped from a scene in a video he recently watched, but he can't remember the exact timestamp of the frame.

Cody has extracted all the frames in the video by FFmpeg, but he knows little about image matching. You, a helpful coder, decide to handle the task to earn an AC in return. Because the picture is stored in a lossy compression format, it is possible that an exact match cannot be found. The goal is to find a position with the smallest sum of squared difference (SSD) for the best match.

If the size of an image $$$I$$$ is $$$W \times H$$$ and the size of a (smaller) template image $$$T$$$ is $$$N \times M$$$, the SSD value of the position $$$(x, y)$$$ is defined as:

$$$\displaystyle\operatorname{SSD}(x, y)=\sum_{i=0}^{N-1}\sum_{j=0}^{M-1} \left(I(x + i, y + j) - T(i, j)\right)^2$$$
(a) $$$I$$$. (b) $$$T$$$. (c) Image difference. $$$\operatorname{SSD}(1,1) = 3^2 + 6^2 = 45$$$.
Input

The first line of the input contains two integers $$$W$$$ and $$$H$$$ — the width and the height of a frame from the video.

The following $$$H$$$ lines contain the description of the image $$$I$$$. Each line contains $$$W$$$ double-digit hexadecimal numbers — the pixels of the corresponding positions.

The next line of the input contains two integers $$$N$$$ and $$$M$$$ — the width and the height of the cropped image.

The following $$$M$$$ lines contain the description of the image $$$T$$$. Each line contains $$$N$$$ double-digit hexadecimal numbers — the pixels of the corresponding positions.

  • $$$1\leq W\leq 1024$$$
  • $$$1\leq H\leq 768$$$
  • $$$0\leq I(x, y)\leq 255$$$
  • $$$1\leq N\leq W$$$
  • $$$1\leq M\leq H$$$
  • $$$0\leq T(x, y)\leq 255$$$
Output

The best matching position $$$(x, y)$$$ $$$(0 \le x \le W - N,\ 0 \le y \le H - M)$$$.

If there are multiple such positions, print any of them.

Examples
Input
3 2
00 FF 12
AA BB 34
2 1
FF 11
Output
1 0
Input
4 5
89 4E 72 C6
C7 E9 EA 8F
6E B1 FD E4
7C 22 6C D0
93 FB DB E5
3 3
79 C0 51
B9 98 37
BB 64 7F
Output
1 0
Input
4 3
14 59 EF A0
83 3E AE 94
06 AA 0C 87
3 2
3E A8 94
A7 0C 87
Output
1 1