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 < 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: 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). For each test case, output a single binary string (r) of length (n - 1): for each (1 \leq i < n), if the (i)-th pair is beautiful, (r_i=1); otherwise, (r_i=0). Do not output spaces. In the first test case, (s = \tt aba), (t = \tt ababa). For (i = 1): Cocoly can split (t = a + ba + ba), so the string pa