#P11016. [2016杭电多校]La Vie en rose

    ID: 10158 传统题 3500ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2200提高+/省选-线性 DP位集加速字符串匹配

[2016杭电多校]La Vie en rose

La Vie en rose

Problem Description

Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string p=p1p2...pmp=p_{1}p_{2}...p_{m}. So, he wants to generate as many as possible pattern strings from pp using the following method:

  1. select some indices i1,i2,...,iki_1,i_2,...,i_k such that 1≤i1<i2<...<ik<∣p∣1 \le i_1 < i_2 < ... < i_k <|p| and ∣ij−ij+1∣>1|i_j-i_{j+1}| > 1 for all 1≤j<k1 \le j < k.
  2. swap pijp_{i_j} and pij+1p_{i_j+1} for all 1≤j≤k1 \le j \le k. Now, for a given a string s=s1s2...sns=s_{1}s_{2}...s_{n}, Professor Zhang wants to find all occurrences of all the generated patterns in ss.

Input

There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case: The first line contains two integers nn and mm (1≤n≤105,1≤m≤min⁡{5000,n})(1 \le n \le 10^5, 1 \le m \le \min\{5000, n\}) -- the length of ss and pp. The second line contains the string ss and the third line contains the string pp. Both the strings consist of only lowercase English letters.

Output

For each test case, output a binary string of length nn. The ii-th character is "1" if and only if the substring sisi+1...si+m−1s_{i}s_{i+1}...s_{i+m-1} is one of the generated patterns.

Sample Input

3
4 1
abac
a
4 2
aaaa
aa
9 3
abcbacacb
abc

Sample Output

1010
1110
100100100

Author

zimpha

Source

2016 Multi-University Training Contest 2