P17581 [JAG 2026 Summer Camp #3] Forbidden Word

You are a highly skilled programmer working in the social media monitoring division of ICPC (International Company of Public Communication), a giant corporation. Your task is to write a program that determines whether a message scheduled to be posted on social media by the public relations department contains a predefined forbidden word. In recent years, numerous social media controversies have been caused by unintended hidden messages that appear when a post is wrapped at a particular number of characters and the characters in each column are read vertically. Forbidden words that appear horizontally within a displayed row must also be avoided. For example, consider the forbidden word `dk` and the message `abcdefghijklmn`. When the viewer's screen width is $10$ characters, the message is displayed as shown in Figure J-1, and `dk` does not appear when the columns are read vertically. However, when the screen width is $7$ characters, the message is displayed as shown in Figure J-2, and reading the fourth column from top to bottom yields `dk`. ```text abcdefghij klmn ``` *Figure J-1: Screen width 10.* ```text abcdefg hijklmn ``` *Figure J-2: Screen width 7.* You are given a string $S$ of length $N$, representing the message to be posted, and a string $T$ of length $M$, representing the forbidden word. Because social media users may view the message on screens of various widths, you must determine whether the message is at risk of causing a controversy for each possible screen width $i$ ($1\le i\le N$). For a screen width of $i$, the string $S$ is displayed with a line break after every $i$ characters, starting from the beginning of the string. More precisely, the $j$-th character of $S$ ($1\le j\le N$) is placed in row $\lfloor(j-1)/i\rfloor+1$ from the top and column $((j-1)\bmod i)+1$ from the left. Note that the last row may contain fewer than $i$ characters. For a screen width of $i$, the message is considered *at risk of causing a controversy* if $T$ occurs as a contiguous substring in the left-to-right reading of some row or in the top-to-bottom reading of some column.

The input contains one or more test cases. The first line of the input contains an integer $t$ ($1\le t\le100$), which is the number of test cases. The descriptions of the $t$ test cases follow, each in the following format. ```text N M S T ``` The first line of each test case contains two integers $N$ and $M$ ($1\le M\le N\le2\times10^5$), representing the lengths of the message and the forbidden word, respectively. The second line contains a string $S$ of length $N$ consisting of lowercase English letters. The third line contains a string $T$ of length $M$ consisting of lowercase English letters. The sum of $N$ over all test cases does not exceed $2\times10^5$, and the sum of $M$ over all test cases does not exceed $2\times10^5$.

For each test case, output a binary string of length $N$. For each $i$ ($1\le i\le N$), the $i$-th character of the string should be `1` if the message is at risk of causing a controversy for a screen width of $i$, and `0` otherwise.