A11751 | Death Stars (medium)

The stardate is 1983, and Princess Heidi is getting better at detecting the Death Stars. This time, two Rebel spies have yet again given Heidi two maps with the possible locations of the Death Star. Since she got rid of all double agents last time, she knows that both maps are correct, and indeed show the map of the solar system that contains the Death Star. However, this time the Empire has hidden the Death Star very well, and Heidi needs to find a place that appears on both maps in order to detect the Death Star.

The first map is an $N×M$ grid, each cell of which shows some type of cosmic object that is present in the corresponding quadrant of space. The second map is an $M×N$ grid. Heidi needs to align those two maps in such a way that they overlap over some $M×M$ section in which all cosmic objects are identical. Help Heidi by identifying where such an $M×M$ section lies within both maps.

The first line of the input contains two space-separated integers $N$ and $M$ ( $1<=N<=2000$ , $1<=M<=200$ , $M<=N$ ). The next $N$ lines each contain $M$ lower-case Latin characters (a-z), denoting the first map. Different characters correspond to different cosmic object types. The next $M$ lines each contain $N$ characters, describing the second map in the same format.

The only line of the output should contain two space-separated integers $i$ and $j$ , denoting that the section of size $M×M$ in the first map that starts at the $i$ -th row is equal to the section of the second map that starts at the $j$ -th column. Rows and columns are numbered starting from 1.

If there are several possible ways to align the maps, Heidi will be satisfied with any of those. It is guaranteed that a solution exists.