题目描述

DreamGrid is learning the insertion operation of a heap in the data structure course.

In the following description, we denote $i/2$ to be the maximum integer $x$ that $2x \le i$. Recall that

• A heap of size $n$ is an array $a_1, a_2, \dots, a_n$ which satisfies one of the following two conditions:
  • For all $2 \le i \le n$, $a_{i/2} \le a_i$. This is called a min heap.
  • For all $2 \le i \le n$, $a_{i/2} \ge a_i$. This is called a max heap.
• The insertion operation can be described by the following pseudo-code: :::align{center} :::

DreamGrid has prepared an initially empty array $a$ as the heap array and $n$ integers $v_1, v_2, \dots, v_n$. He is just about to insert these $n$ integers into the heap array in order when his cellphone rings, so he leaves this work to his roommate BaoBao.

Unfortunately, BaoBao doesn't understand what the argument $is\_max$ means in the insertion function (but for our dear contestants, we hope that you've understood the meaning of this argument), so he generates a binary string (a string which only contains 0 and 1) $b = b_1b_2\dots b_n$ of length $n$, where $b_i$ indicates the $i$-th character in the string, and decides the value of $is\_max$ according to the string. When inserting $v_i$ into $a$, if $b_i$ equals to 0, then $is\_max$ $\textbf{during this insertion}$ will be false; otherwise if $b_i$ equals to 1, then $is\_max$ $\textbf{during this insertion}$ will be true.

When DreamGrid comes back, he finds with dismay that the final heap array $a_1, a_2 \dots, a_n$ does not seem to be a valid heap! Given the $n$ inserted integers $v_1, v_2, \dots, v_n$, the final array and given that BaoBao has inserted $v_1, v_2, \dots, v_n$ in order, please help DreamGrid restore the binary string $b$ BaoBao generates.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the size of the final array.

The second line contains $n$ integers $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 10^9$), indicating the integers in the order they are inserted.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$, which is a permutation of $v_1, v_2, \dots, v_n$, indicating the final heap array.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

输出格式

For each test case output one line containing one binary string, indicating the string BaoBao generates for inserting the integers. If there are multiple valid answers, output the one with the smallest lexicographic order. If the binary string does not exist, output Impossible (without quotes) instead.

Recall that, for two binary strings $s$ and $t$ of length $n$, we say $s$ is lexicographically smaller than $t$, if there exists an integer $k$ satisfying all the following constraints:

• $1 \le k \le n$.
• For all $1 \le i < k$, $s_i = t_i$.
• $s_k = \text{`0'}$ and $t_k = \text{`1'}$.

3
4
2 3 1 4
4 1 3 2
5
4 5 1 2 3
3 4 1 5 2
3
1 1 2
2 1 1

0101
Impossible
001

提示

We now explain the first sample test case.

$$\begin{array}{|c|c|c|c|} \hline \textbf{$i$} & \textbf{$v_i$} & \textbf{$b_i$} & \textbf{``Heap'' Array after Insertion} \\ \hline 1 & 2 & 0 & \{2\} \\ \hline 2 & 3 & 1 & \{3, 2\} \\ \hline 3 & 1 & 0 & \{1, 2, 3\} \\ \hline 4 & 4 & 1 & \{4, 1, 3, 2\} \\ \hline \end{array}$$