Problem Description

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.

abcdefghij
klmn

Figure J-1: Screen width 10.

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.

Input Format

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.

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

Output Format

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.

5
14 2
abcdefghijklmn
dk
6 3
banana
ana
10 2
ababababab
aa
11 4
mississippi
issi
8 3
aaaaaaaa
aaa

00000010000000
101111
0101010100
11011111111
11111111