Codeforces Round 390 (Div. 2)
E
Dasha and cyclic table
Codeforces
2600
原题
← D→
翻译中…

Dasha is fond of challenging puzzles: Rubik's Cube $3 × 3 × 3$, $4 × 4 × 4$, $5 × 5 × 5$ and so on. This time she has a cyclic table of size $*n* × *m*$, and each cell of the table contains a lowercase English letter. Each cell has coordinates $(*i*, *j*)$ ($0 ≤ *i* < *n*$, $0 ≤ *j* < *m*$). The table is cyclic means that to the right of cell $(*i*, *j*)$ there is the cell image, and to the down there is the cell image.

翻译中…

Dasha has a pattern as well. A pattern is a non-cyclic table of size $*r* × *c*$. Each cell is either a lowercase English letter or a question mark. Each cell has coordinates $(*i*, *j*)$ ($0 ≤ *i* < *r*$, $0 ≤ *j* < *c*$).

翻译中…

The goal of the puzzle is to find all the appearance positions of the pattern in the cyclic table.

翻译中…

We say that the cell $(*i*, *j*)$ of cyclic table is an appearance position, if for every pair $(*x*, *y*)$ such that $0 ≤ *x* < *r*$ and $0 ≤ *y* < *c*$ one of the following conditions holds:

翻译中…
  • There is a question mark in the cell $(*x*, *y*)$ of the pattern, or
  • The cell image of the cyclic table equals to the cell $(*x*, *y*)$ of the pattern.
翻译中…

Dasha solved this puzzle in no time, as well as all the others she ever tried. Can you solve it?.

翻译中…

Input

翻译中…

The first line contains two integers $*n*$ and $*m*$ ($1 ≤ *n*, *m* ≤ 400$) — the cyclic table sizes.

翻译中…

Each of the next $*n*$ lines contains a string of $*m*$ lowercase English characters — the description of the cyclic table.

翻译中…

The next line contains two integers $*r*$ and $*c*$ ($1 ≤ *r*, *c* ≤ 400$) — the sizes of the pattern.

翻译中…

Each of the next $*r*$ lines contains a string of $*c*$ lowercase English letter and/or characters '?' — the description of the pattern.

翻译中…

Output

翻译中…

Print $*n*$ lines. Each of the $*n*$ lines should contain $*m*$ characters. Each of the characters should equal '0' or '1'.

翻译中…

The $*j*$-th character of the $*i*$-th ($0$-indexed) line should be equal to '1', in case the cell $(*i*, *j*)$ is an appearance position, otherwise it should be equal to '0'.

翻译中…

样例

Input #1
5 7
qcezchs
hhedywq
wikywqy
qckrqzt
bqexcxz
3 2
??
yw
?q
Output #1
0000100
0001001
0000000
0000000
0000000
InputCopy OutputCopy
Input #2
10 10
fwtoayylhw
yyaryyjawr
ywrdzwhscy
hnsyyxiphn
bnjwzyyjvo
kkjgseenwn
gvmiflpcsy
lxvkwrobwu
wyybbcocyy
yysijsvqry
2 2
??
yy
Output #2
1000100000
0000000001
0001000000
0000010000
0000000000
0000000000
0000000000
0100000010
1000000001
0000010000
InputCopy OutputCopy
Input #3
8 6
ibrgxl
xqdcsg
okbcgi
tvpetc
xgxxig
igghzo
lmlaza
gpswzv
1 4
gx??
Output #3
000100
000001
000000
000000
010001
000000
000000
000000
InputCopy OutputCopy
题目信息
题号
754E
时间限制
6 s
内存限制
512 MB
标签
位运算
暴力
FFT
字符串
树

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。