G. 朴素字符串划分

时间限制：每个测试点 $10$ 秒 内存限制：每个测试点 $1024$ 兆字节

而我将：爱你所爱的人间；愿你所愿的笑颜。你的手我蹒跚在牵，请带我去明天。 —— 王菲《如愿》

Cocoly 有一个长度为 $m$ 的字符串 $t$ ，仅由小写英文字母组成，他想把它划分成若干段。

如果存在一个字符串序列 $a_1,a_2,\dots,a_k$ ，满足：

$t = a_1 + a_2 + \dots + a_k$ ，其中 $+$ 表示字符串拼接；
对于每个 $1 \le i \le k$ ，至少满足 $a_i = x$ 或 $a_i = y$ 之一；

则称字符串对 $(x,y)$ 是优美的。

Cocoly 还有一个长度为 $n$ 的字符串 $s$ 。现在，对于每个 $1 \le i < n$ ，你需要判断：字符串对

(s_1s_2\dots s_i,\ s_{i+1}s_{i+2}\dots s_n)

是否是优美的。

注意：由于输入输出量较大，你需要对其进行优化。例如在 C++ 中，在 main() 函数开头加入以下代码即可：

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

输入格式

每个测试包含多组测试数据。第一行一个整数 $T$ （ $1 \le T \le 10^5$ ）—— 测试数据组数。

每组测试数据：

第一行两个整数 $n,m$ （ $2 \le n \le m \le 5 \cdot 10^6$ ）—— 分别表示字符串 $s$ 和 $t$ 的长度。
第二行一个字符串 $s$ ，长度为 $n$ 。
第三行一个字符串 $t$ ，长度为 $m$ 。

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

输出格式

对于每组测试数据，输出一个长度为 $n-1$ 的二进制字符串：

若第 $i$ 个分割点对应的字符串对是优美的，则第 $i$ 位为 $\boldsymbol{1}$ ；
否则为 $\boldsymbol{0}$ 。

输出中不要包含空格。

样例输入

7
3 5
aba
ababa
4 10
czzz
czzzzzczzz
5 14
dream
dredreamamamam
5 18
tcccc
tcctccccctccctcccc
7 11
abababc
abababababc
7 26
aaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
19 29
bbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbb

样例输出

11
011
0010
0000
010100
111111
110010001100010011

样例解释

第一个测试用例： $s = \texttt{aba}$ ， $t = \texttt{ababa}$ 。

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

第二个测试用例： $s = \texttt{czzz}$ ， $t = \texttt{czzzzzczzz}$ 。

对于 $i=1$ ：不存在使用 $\texttt{c}$ 和 $\texttt{zzz}$ 划分 $t$ 的合法方案。
对于 $i=2$ ：可以将 $t$ 划分为 $\texttt{cz+zz+zz+cz+zz}$ 。
对于 $i=3$ ：可以将 $t$ 划分为 $\texttt{czz+z+z+z+czz+z}$ 。

#CF2053G. 朴素字符串划分

朴素字符串划分