← 返回题目列表

Codeforces · 754/E

E. 大傻和循环表

中文机器翻译题面 查看原题

达莎喜欢挑战拼图:魔方3×3×3、4×4×4、5×5×5等。这次她有一个大小为 n × m 的循环表,表的每个单元格包含一个小写英文字母。每个单元格都有坐标 (i, j) (0 ≤ i < n, 0 ≤ j < m)。该表是循环的,意味着单元格 (i, j) 的右侧是单元格 $$(i,(j+1)\bmod m)$$,下方是单元格 $$( ( i + 1 ) \bmod n, j )$$。

大傻也有图案。模式是大小为 r × c 的非循环表。每个单元格要么是小写英文字母,要么是问号。每个单元格都有坐标 (i, j) (0 ≤ i < r, 0 ≤ j < c)。

拼图的目标是找到循环表中模式的所有出现位置。

如果对于每对 (x, y) 使得 0 ≤ x < r 且 0 ≤ y < c 满足以下条件之一,则我们说循环表的单元格 (i, j) 是出现位置:

- 模式的单元格 (x, y) 中有一个问号,或者
- 循环表的单元格 $$( ( i + x ) \bmod n, ( j + y ) \bmod m )$$ 等于模式的单元格 (x, y)。

Dasha 很快就解决了这个难题,以及她尝试过的所有其他难题。能解决吗?

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 400) — 循环表大小。

接下来的 n 行每一行都包含 m 个小写英文字符的字符串——循环表的描述。

下一行包含两个整数 r 和 c (1 ≤ r, c ≤ 400) — 图案的大小。

接下来的 r 行包含一串 c 个小写英文字母和/或字符 '?' — 模式的描述。

输出

打印 n 行。 n 行中的每一行应包含 m 个字符。每个字符应等于“0”或“1”。

如果单元格 (i, j) 是出现位置,则第 i(0 索引)行的第 j 个字符应等于“1”,否则应等于“0”。

示例

输入 #1

5 7
qcezchs
hhedywq
wikywqy
qckrqzt
bqexcxz
3 2
??
yw
?q

输出 #1

0000100
0001001
0000000
0000000
0000000

输入 #2

10 10
fwtoayylhw
yyaryyjawr
ywrdzwhscy
hnsyyxiphn
bnjwzyyjvo
kkjgseenwn
gvmiflpcsy
lxvkwrobwu
wyybbcocyy
yysijsvqry
2 2
??
yy

输出 #2

1000100000
0000000001
0001000000
0000010000
0000000000
0000000000
0000000000
0100000010
1000000001
0000010000

输入 #3

8 6
ibrgxl
xqdcsg
okbcgi
tvpetc
xgxxig
igghzo
lmlaza
gpswzv
1 4
gx??

输出 #3

000100
000001
000000
000000
010001
000000
000000
000000