Cocoly has a string $t$ of length $m$, consisting of lowercase English letters, and he would like to split it into parts. He calls a pair of strings $(x, y)$ beautiful if and only if there exists a sequence of strings $a_1, a_2, \ldots, a_k$, such that:

• $t = a_1 + a_2 + \ldots + a_k$, where $+$ denotes string concatenation.
• For each $1 \leq i \leq k$, at least one of the following holds: $a_i = x$, or $a_i = y$.

Cocoly has another string $s$ of length $n$, consisting of lowercase English letters. Now, for each $1 \leq i < n$, Cocoly wants you to determine whether the pair of strings $(s_1s_2 \ldots s_i, \, s_{i+1}s_{i+2} \ldots s_n)$ is beautiful.

Note: since the input and output are large, you may need to optimize them for this problem.

For example, in C++, it is enough to use the following lines at the start of the main() function:

Input

Each test contains multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq m \leq 5 \cdot 10^6$) — the lengths of $s$ and the length of $t$.

The second line of each test case contains a single string $s$ of length $n$, consisting only of lowercase English letters.

The third line of each test case contains a single string $t$ of length $m$, consisting only of lowercase English letters.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^7$.

Output

For each test case, output a single binary string $r$ of length $n - 1$: for each $1 \leq i < n$, if the $i$-th pair is beautiful, $r_i=\texttt{1}$; otherwise, $r_i=\texttt{0}$. Do not output spaces.

见题面 Input 部分

见题面 Output 部分

In the first test case, $s = \tt$, $t = \tt$.

• For $i = 1$: Cocoly can split $t = \texttt{a} + \texttt{ba} + \texttt{ba}$, so the string pair $(\texttt{a}, \texttt{ba})$ is beautiful.
• For $i = 2$: Cocoly can split $t = \texttt{ab} + \texttt{ab} + \texttt{a}$, so the string pair $(\texttt{ab}, \texttt{a})$ is beautiful.

In the second test case, $s = \tt$, $t = \tt$.

• For $i = 1$: It can be proven that there is no solution to give a partition of $t$ using strings $\texttt{c}$ and $\texttt{zzz}$.
• For $i = 2$: Cocoly can split $t$ into $\texttt{cz} + \texttt{zz} + \texttt{zz} + \texttt{cz} + \texttt{zz}$.
• For $i = 3$: Cocoly can split $t$ into $\texttt{czz} + \texttt{z} + \texttt{z} + \texttt{z} + \texttt{czz} + \texttt{z}$.