{"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 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 .\n\nDasha 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_).\n\nThe goal of the puzzle is to find all the appearance positions of the pattern in the cyclic table.\n\nWe 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:\n\n*   There is a question mark in the cell (_x_, _y_) of the pattern, or\n*   The cell of the cyclic table equals to the cell (_x_, _y_) of the pattern.\n\nDasha solved this puzzle in no time, as well as all the others she ever tried. Can you solve it?.\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 400) — the cyclic table sizes.\n\nEach of the next _n_ lines contains a string of _m_ lowercase English characters — the description of the cyclic table.\n\nThe next line contains two integers _r_ and _c_ (1 ≤ _r_, _c_ ≤ 400) — the sizes of the pattern.\n\nEach of the next _r_ lines contains a string of _c_ lowercase English letter and/or characters '_?_' — the description of the pattern.\n\n## Output\n\nPrint _n_ lines. Each of the _n_ lines should contain _m_ characters. Each of the characters should equal '_0_' or '_1_'.\n\nThe _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_'.\n\n[samples]","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[0 ≤ j < m]）。该表格是循环的，意味着单元格 #cf_span[(i, j)] 的右侧是单元格 #cf_span[(i, (j+1) \\bmod m)]，下方是单元格 #cf_span[((i+1) \\bmod n, j)]。\n\nDasha 还有一个模式。模式是一个大小为 #cf_span[r × c] 的非循环表格。每个单元格要么是一个小写英文字母，要么是一个问号。每个单元格的坐标为 #cf_span[(i, j)]（#cf_span[0 ≤ i < r]，#cf_span[0 ≤ j < c]）。\n\n谜题的目标是找出模式在循环表格中的所有出现位置。\n\n我们称循环表格中的单元格 #cf_span[(i, j)] 是一个出现位置，当且仅当对于每一对 #cf_span[(x, y)] 满足 #cf_span[0 ≤ x < r] 且 #cf_span[0 ≤ y < c]，以下条件之一成立：\n\nDasha 在瞬间就解决了这个谜题，以及她曾经尝试过的所有其他谜题。你能解决它吗？\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 400]）——循环表格的尺寸。\n\n接下来的 #cf_span[n] 行每行包含一个由 #cf_span[m] 个小写英文字母组成的字符串——循环表格的描述。\n\n下一行包含两个整数 #cf_span[r] 和 #cf_span[c]（#cf_span[1 ≤ r, c ≤ 400]）——模式的尺寸。\n\n接下来的 #cf_span[r] 行每行包含一个由 #cf_span[c] 个小写英文字母和/或字符 '_?_' 组成的字符串——模式的描述。\n\n请输出 #cf_span[n] 行。每行应包含 #cf_span[m] 个字符，每个字符应为 '_0_' 或 '_1_'。\n\n第 #cf_span[i] 行（0-索引）的第 #cf_span[j] 个字符应为 '_1_'，当且仅当单元格 #cf_span[(i, j)] 是一个出现位置；否则应为 '_0_'。\n\n## Input\n\n第一行包含两个整数 #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] 个小写英文字母和/或字符 '_?_' 组成的字符串——模式的描述。\n\n## Output\n\n请输出 #cf_span[n] 行。每行应包含 #cf_span[m] 个字符，每个字符应为 '_0_' 或 '_1_'。第 #cf_span[i] 行（0-索引）的第 #cf_span[j] 个字符应为 '_1_'，当且仅当单元格 #cf_span[(i, j)] 是一个出现位置；否则应为 '_0_'。\n\n[samples]","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.  \nLet $ r, c \\in \\mathbb{Z}^+ $ be the dimensions of the pattern.  \nLet $ P \\in (\\Sigma \\cup \\{?\\})^{r \\times c} $ be the pattern, where $ ? $ is a wildcard matching any letter.  \n\nThe 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) $.  \n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 400 $  \n2. $ 1 \\leq r, c \\leq 400 $  \n3. For all $ (i,j) \\in [0,n) \\times [0,m) $, $ T[i][j] \\in \\Sigma $  \n4. For all $ (x,y) \\in [0,r) \\times [0,c) $, $ P[x][y] \\in \\Sigma \\cup \\{?\\} $  \n\n**Objective**  \nFor 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) $:  \n$$\nT[(i+x) \\bmod n][(j+y) \\bmod m] = P[x][y] \\quad \\text{or} \\quad P[x][y] = ?\n$$  \nOutput an $ n \\times m $ binary matrix $ B $, where:  \n$$\nB[i][j] = \n\\begin{cases}\n1 & \\text{if } (i,j) \\text{ is an appearance position} \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF754E","tags":["bitmasks","brute force","fft","strings","trees"],"sample_group":[["5 7\nqcezchs\nhhedywq\nwikywqy\nqckrqzt\nbqexcxz\n3 2\n??\nyw\n?q","0000100\n0001001\n0000000\n0000000\n0000000"],["10 10\nfwtoayylhw\nyyaryyjawr\nywrdzwhscy\nhnsyyxiphn\nbnjwzyyjvo\nkkjgseenwn\ngvmiflpcsy\nlxvkwrobwu\nwyybbcocyy\nyysijsvqry\n2 2\n??\nyy","1000100000\n0000000001\n0001000000\n0000010000\n0000000000\n0000000000\n0000000000\n0100000010\n1000000001\n0000010000"],["8 6\nibrgxl\nxqdcsg\nokbcgi\ntvpetc\nxgxxig\nigghzo\nlmlaza\ngpswzv\n1 4\ngx??","000100\n000001\n000000\n000000\n010001\n000000\n000000\n000000"]],"created_at":"2026-03-03 11:00:39"}}