Two Binary Strings Problem

题号：NC231129
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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 , denoting the number of the test cases.

For each test case:

The first line contains one integer , denoting the length of the two binary strings.

The second line contains one binary string .

The third line contains one binary string .

It is guaranteed that .

输出描述:

For each test case:

Output one line containing a binary string  of length , where  iff  is lucky while  iff  is not lucky.

示例1

输入

复制

输出

复制

01000
00001100