CF2053G.Naive String Splits

And I will: love the world that you've adored; wish the smile that you've longed for. Your hand in mine as we explore, please take me to tomorrow's shore.

— Faye Wong, As Wished

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 \lt 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:

int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr); std::cout.tie(nullptr);}

我愿：爱你所爱的世界，许你所盼的微笑。携手共赴未知之旅，请带我抵达明日之岸。

——王菲《如愿》（视频链接）

Cocoly 有一个长度为 $m$ 的字符串 $t$，仅由小写英文字母组成，他希望将其分割为若干段。我们称一对字符串 $(x, y)$ 是优美的，当且仅当存在一个字符串序列 $a_1, a_2, \ldots, a_k$，满足：

• $t = a_1 + a_2 + \ldots + a_k$，其中 $+$ 表示字符串连接；
• 对每个 $1 \leq i \leq k$，以下条件至少有一个成立：$a_i = x$ 或 $a_i = y$。

Cocoly 还有另一个长度为 $n$ 的字符串 $s$，也仅由小写英文字母组成。现在，对每个 $1 \leq i < n$，你需要判断字符串对 $(s_1s_2 \ldots s_i,\, s_{i+1}s_{i+2} \ldots s_n)$ 是否是优美的。

注意：由于输入与输出规模较大，你可能需要对此题进行输入/输出优化。

例如，在 C++ 中，只需在 main() 函数开头加入如下几行代码即可：

int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr); std::cout.tie(nullptr);}

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

每个测试包含多个测试用例。第一行包含一个整数 $T$（$1 \leq T \leq 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq m \leq 5 \cdot 10^6$），分别表示字符串 $s$ 和字符串 $t$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。

每个测试用例的第三行包含一个长度为 $m$ 的字符串 $t$，仅由小写英文字母组成。

保证所有测试用例中 $m$ 的总和不超过 $10^7$。

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

对于每个测试用例，输出一个长度为 $n - 1$ 的二进制字符串 $r$：对每个 $1 \leq i \lt n$，若第 $i$ 个数对是优美的，则 $r_i=\texttt{1}$；否则 $r_i=\texttt{0}$。不要输出空格。

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

• 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 czzz$, $t = \tt czzzzzczzz$.

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

在第一个测试用例中，$s = \tt aba$，$t = \tt ababa$。

• 对于 $i = 1$：Cocoly 可以将 $t$ 拆分为 $\texttt{a} + \texttt{ba} + \texttt{ba}$，因此字符串对 $(\texttt{a}, \texttt{ba})$ 是优美的。
• 对于 $i = 2$：Cocoly 可以将 $t$ 拆分为 $\texttt{ab} + \texttt{ab} + \texttt{a}$，因此字符串对 $(\texttt{ab}, \texttt{a})$ 是优美的。

在第二个测试用例中，$s = \tt czzz$，$t = \tt czzzzzczzz$。

• 对于 $i = 1$：可以证明，不存在使用字符串 $\texttt{c}$ 和 $\texttt{zzz}$ 对 $t$ 进行划分的方案。
• 对于 $i = 2$：Cocoly 可以将 $t$ 拆分为 $\texttt{cz} + \texttt{zz} + \texttt{zz} + \texttt{cz} + \texttt{zz}$。
• 对于 $i = 3$：Cocoly 可以将 $t$ 拆分为 $\texttt{czz} + \texttt{z} + \texttt{z} + \texttt{z} + \texttt{czz} + \texttt{z}$。