Codeforces Round 390 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

brute force

fft

strings

trees

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Dasha and cyclic table

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputDasha 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 , and to the down there is the cell .

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 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'.

Examples

Input

5 7

qcezchs

hhedywq

wikywqy

qckrqzt

bqexcxz

3 2

??

yw

?q

Output

0000100

0001001

0000000

0000000

0000000

Input

10 10

fwtoayylhw

yyaryyjawr

ywrdzwhscy

hnsyyxiphn

bnjwzyyjvo

kkjgseenwn

gvmiflpcsy

lxvkwrobwu

wyybbcocyy

yysijsvqry

2 2

??

yy

Output

1000100000

0000000001

0001000000

0000010000

0000000000

0000000000

0000000000

0100000010

1000000001

0000010000

Input

8 6

ibrgxl

xqdcsg

okbcgi

tvpetc

xgxxig

igghzo

lmlaza

gpswzv

1 4

gx??

Output

000100

000001

000000

000000

010001

000000

000000

000000

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 19:39:40 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|