English · Original
Chinese · Translation
Formal · Original
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 , 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_'.
[samples]
Dasha 喜欢挑战谜题：三阶魔方 #cf_span[3 × 3 × 3]、四阶魔方 #cf_span[4 × 4 × 4]、五阶魔方 #cf_span[5 × 5 × 5] 等等。这次她面对的是一个大小为 #cf_span[n × m] 的循环表格，表格中每个单元格包含一个小写英文字母。每个单元格的坐标为 #cf_span[(i, j)]（#cf_span[0 ≤ i < n]，#cf_span[0 ≤ j < m]）。该表格是循环的，意味着单元格 #cf_span[(i, j)] 的右侧是单元格 #cf_span[(i, (j+1) \bmod m)]，下方是单元格 #cf_span[((i+1) \bmod n, j)]。
Dasha 还有一个模式。模式是一个大小为 #cf_span[r × c] 的非循环表格。每个单元格要么是一个小写英文字母，要么是一个问号。每个单元格的坐标为 #cf_span[(i, j)]（#cf_span[0 ≤ i < r]，#cf_span[0 ≤ j < c]）。
谜题的目标是找出模式在循环表格中的所有出现位置。
我们称循环表格中的单元格 #cf_span[(i, j)] 是一个出现位置，当且仅当对于每一对 #cf_span[(x, y)] 满足 #cf_span[0 ≤ x < r] 且 #cf_span[0 ≤ y < c]，以下条件之一成立：
Dasha 在瞬间就解决了这个谜题，以及她曾经尝试过的所有其他谜题。你能解决它吗？
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 400]）——循环表格的尺寸。
接下来的 #cf_span[n] 行每行包含一个由 #cf_span[m] 个小写英文字母组成的字符串——循环表格的描述。
下一行包含两个整数 #cf_span[r] 和 #cf_span[c]（#cf_span[1 ≤ r, c ≤ 400]）——模式的尺寸。
接下来的 #cf_span[r] 行每行包含一个由 #cf_span[c] 个小写英文字母和/或字符 '_?_' 组成的字符串——模式的描述。
请输出 #cf_span[n] 行。每行应包含 #cf_span[m] 个字符，每个字符应为 '_0_' 或 '_1_'。
第 #cf_span[i] 行（0-索引）的第 #cf_span[j] 个字符应为 '_1_'，当且仅当单元格 #cf_span[(i, j)] 是一个出现位置；否则应为 '_0_'。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 400]）——循环表格的尺寸。接下来的 #cf_span[n] 行每行包含一个由 #cf_span[m] 个小写英文字母组成的字符串——循环表格的描述。下一行包含两个整数 #cf_span[r] 和 #cf_span[c]（#cf_span[1 ≤ r, c ≤ 400]）——模式的尺寸。接下来的 #cf_span[r] 行每行包含一个由 #cf_span[c] 个小写英文字母和/或字符 '_?_' 组成的字符串——模式的描述。
## Output
请输出 #cf_span[n] 行。每行应包含 #cf_span[m] 个字符，每个字符应为 '_0_' 或 '_1_'。第 #cf_span[i] 行（0-索引）的第 #cf_span[j] 个字符应为 '_1_'，当且仅当单元格 #cf_span[(i, j)] 是一个出现位置；否则应为 '_0_'。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the cyclic table.
Let $ T \in \Sigma^{n \times m} $ be the cyclic table, where $ \Sigma $ is the set of lowercase English letters.
Let $ r, c \in \mathbb{Z}^+ $ be the dimensions of the pattern.
Let $ P \in (\Sigma \cup \{?\})^{r \times c} $ be the pattern, where $ ? $ is a wildcard matching any letter.
The table is cyclic: for any $ (i, j) $, the right neighbor is $ (i, (j+1) \bmod m) $ and the down neighbor is $ ((i+1) \bmod n, j) $.
**Constraints**
1. $ 1 \leq n, m \leq 400 $
2. $ 1 \leq r, c \leq 400 $
3. For all $ (i,j) \in [0,n) \times [0,m) $, $ T[i][j] \in \Sigma $
4. For all $ (x,y) \in [0,r) \times [0,c) $, $ P[x][y] \in \Sigma \cup \{?\} $
**Objective**
For each position $ (i, j) \in [0,n) \times [0,m) $, determine if it is an *appearance position*, i.e., for all $ (x,y) \in [0,r) \times [0,c) $:
$$
T[(i+x) \bmod n][(j+y) \bmod m] = P[x][y] \quad \text{or} \quad P[x][y] = ?
$$
Output an $ n \times m $ binary matrix $ B $, where:
$$
B[i][j] =
\begin{cases}
1 & \text{if } (i,j) \text{ is an appearance position} \\
0 & \text{otherwise}
\end{cases}
$$
API Response (JSON)
{
"problem": {
"name": "E. Dasha and cyclic table",
"description": {
"content": "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 Englis",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 6000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF754E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 Englis...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Dasha 喜欢挑战谜题：三阶魔方 #cf_span[3 × 3 × 3]、四阶魔方 #cf_span[4 × 4 × 4]、五阶魔方 #cf_span[5 × 5 × 5] 等等。这次她面对的是一个大小为 #cf_span[n × m] 的循环表格，表格中每个单元格包含一个小写英文字母。每个单元格的坐标为 #cf_span[(i, j)]（#cf_span[0 ≤ i < n]，#cf_span...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the cyclic table. \nLet $ T \\in \\Sigma^{n \\times m} $ be the cyclic table, where $ \\Sigma $ is the set of lowercase English letters...",
"is_translate": false,
"language": "Formal"
}
]
}