write a go solution for G. Naive String Splitstime limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputAnd 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 WishedCocoly 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<=qi<=qk, 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<=i<n, Cocoly wants you to determine whether the pair of strings (s_1s_2ldotss_i,,s_i+1s_i+2ldotss_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:int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr); std::cout.tie(nullptr);}InputEach test contains multiple test cases. The first line contains an integer T (1<=T<=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<=n<=m<=5*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.OutputFor each test case, output a single binary string r of length n-1: for each 1<=i<n, if the i-th pair is beautiful, r_i=texttt1; otherwise, r_i=texttt0. Do not output spaces.ExampleInput73 5abaababa4 10czzzczzzzzczzz5 14dreamdredreamamamam5 18tcccctcctccccctccctcccc7 11abababcabababababc7 26aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa19 29bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbOutput11
011
0010
0000
010100
111111
110010001100010011
NoteIn the first test case, s=ttaba, t=ttababa.  For i=1: Cocoly can split t=texttta+textttba+textttba, so the string pair (texttta,textttba) is beautiful.  For i=2: Cocoly can split t=textttab+textttab+texttta, so the string pair (textttab,texttta) is beautiful. In the second test case, s=ttczzz, t=ttczzzzzczzz.  For i=1: It can be proven that there is no solution to give a partition of t using strings textttc and textttzzz.  For i=2: Cocoly can split t into textttcz+textttzz+textttzz+textttcz+textttzz.  For i=3: Cocoly can split t into textttczz+textttz+textttz+textttz+textttczz+textttz.. Output only the code with no comments, explanation, or additional text.