G. Word Search
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Find parts of a 2d grid matching a 2d word.

Input

  • One line containing the number of rows and columns in the search key, $$$r_k$$$ and $$$c_k$$$ ($$$1 \le r, c \le 2000$$$).
  • $$$r_k$$$ further lines, each containing $$$c_k$$$ Latin characters comprising a row of the search key.
  • One line containing the number of rows and columns in the haystack, $$$r_h$$$ and $$$c_h$$$ ($$$r_k \le r_h \le 2000$$$, $$$c_k \le c_h \le 2000$$$).
  • $$$r_h$$$ further lines, each containing $$$c_h$$$ Latin characters comprising a row of the search key.
Output

Illustrate the matching areas of the haystack by printing a grid of the same size. In locations that are part of at least one match, print the original character from the haystack. In other cases, print a full-stop "." character.

Examples
Input
3 3
ghi
lmn
qrs
5 5
abcde
fghij
klmno
pqrst
uvwxy
Output
.....
.ghi.
.lmn.
.qrs.
.....
Input
1 2
ab
6 4
abba
baab
abba
baab
abba
baab
Output
ab..
..ab
ab..
..ab
ab..
..ab
Input
4 1
n
a
n
a
7 6
ananan
nanana
ananan
nanana
ananan
nanana
batman
Output
.n.n.n
nanana
ananan
nanana
ananan
.a.ana
....a.
Input
2 2
oo
oo
5 5
xoooo
oxooo
ooxoo
oooxo
oooox
Output
..ooo
..ooo
oo.oo
ooo..
ooo..