409145: GYM103446 J Two Binary Strings Problem

Given an integer $$$n$$$ and two binary strings $$$a_1a_2\cdots a_n$$$ (denoted by $$$A$$$) and $$$b_1b_2\cdots b_n$$$ (denoted by $$$B$$$) of length $$$n$$$.

Define function: $$$$$$ f(l,r)=\begin{cases} 1,& \text{if}\;\sum\limits_{i=l}^r a_i > \frac{r-l+1}{2} \\ 0,&\text{otherwise}

\end{cases} $$$$$$

We say an integer $$$k$$$ is lucky, iff for each $$$i\,(1\le i \le n)$$$, $$$f\big(\max(i-k+1,1),i \big)=b_i$$$ holds.

For each integer $$$k\,(1\le k \le n)$$$, determine if it is lucky.

The first line contains one integer $$$T\,(1\le T \le 50000)$$$, denoting the number of the test cases.

For each test case:

The first line contains one integer $$$n\,(1\le n \le 50000)$$$, denoting the length of the two binary strings.

The second line contains one binary string $$$A$$$.

The third line contains one binary string $$$B$$$.

It is guaranteed that $$$\sum n \le 50000$$$.

For each test case:

Output one line containing a binary string $$$c_1c_2\cdots c_n$$$ of length $$$n$$$, where $$$c_i=1$$$ iff $$$i$$$ is lucky while $$$c_i=0$$$ iff $$$i$$$ is not lucky.

2
5
11010
11000
8
11110000
11111100

01000
00001100