Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

G. Naive String Splits
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
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 a1,a2,,ak, such that:

  • t=a1+a2++ak, where + denotes string concatenation.
  • For each 1ik, at least one of the following holds: ai=x, or ai=y.

Cocoly has another string s of length n, consisting of lowercase English letters. Now, for each 1i<n, Cocoly wants you to determine whether the pair of strings (s1s2si,si+1si+2sn) 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);
}
Input

Each test contains multiple test cases. The first line contains an integer T (1T105) — 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 (2nm5106) — 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 107.

Output

For each test case, output a single binary string r of length n1: for each 1i<n, if the i-th pair is beautiful, ri=1; otherwise, ri=0. Do not output spaces.

Example
Input
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
Output
11
011
0010
0000
010100
111111
110010001100010011
Note

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

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

In the second test case, s=czzz, t=czzzzzczzz.

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