题目描述

你是一名技术高超的程序员，在大型企业 ICPC（International Company of Public Communication，国际公共传播公司）的社交媒体监控部门工作。你的任务是编写一个程序，判断公关部门计划在社交媒体上发布的消息是否包含一个预先指定的禁用词。

近年来，许多社交媒体争议源于无意中隐藏的信息：将一条帖子按特定字符数换行后，逐列竖直阅读其中的字符，就可能出现这样的信息。同时，也必须避免禁用词在显示出来的某一行中横向出现。

例如，考虑禁用词 dk 和消息 abcdefghijklmn。当读者的屏幕宽度为 $10$ 个字符时，消息的显示方式如图 J-1 所示，竖直阅读各列时不会出现 dk。然而，当屏幕宽度为 $7$ 个字符时，消息的显示方式如图 J-2 所示，从上到下阅读第四列便会得到 dk。

abcdefghij
klmn

图 J-1：屏幕宽度为 10。

abcdefg
hijklmn

图 J-2：屏幕宽度为 7。

给定长度为 $N$ 的字符串 $S$，表示将要发布的消息，以及长度为 $M$ 的字符串 $T$，表示禁用词。由于社交媒体用户可能使用不同宽度的屏幕查看消息，对于每一种可能的屏幕宽度 $i$（$1\le i\le N$），你都需要判断消息是否存在引发争议的风险。

当屏幕宽度为 $i$ 时，从字符串开头开始，每显示 $i$ 个字符后换行。更准确地说，$S$ 的第 $j$ 个字符（$1\le j\le N$）会被放在从上到下的第 $\lfloor(j-1)/i\rfloor+1$ 行，以及从左到右的第 $((j-1)\bmod i)+1$ 列。注意，最后一行可能不足 $i$ 个字符。

对于屏幕宽度 $i$，如果从左到右阅读某一行，或从上到下阅读某一列时，$T$ 作为连续子串出现，则认为该消息存在引发争议的风险。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 $t$（$1\le t\le100$），表示测试数据的组数。接下来依次给出 $t$ 组测试数据，每组格式如下。

N M
S
T

每组测试数据的第一行包含两个整数 $N,M$（$1\le M\le N\le2\times10^5$），分别表示消息和禁用词的长度。第二行包含一个长度为 $N$、由小写英文字母组成的字符串 $S$。第三行包含一个长度为 $M$、由小写英文字母组成的字符串 $T$。

所有测试数据的 $N$ 之和不超过 $2\times10^5$，$M$ 之和也不超过 $2\times10^5$。

输出格式

对于每组测试数据，输出一个长度为 $N$ 的二进制字符串。对于每个 $i$（$1\le i\le N$），如果屏幕宽度为 $i$ 时消息存在引发争议的风险，则字符串的第 $i$ 个字符应为 1；否则应为 0。

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