Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4119

Time Limit: 1 Second      Memory Limit: 65536 KB

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:

    procedure insert(
      $v$: value to insert,
      $a$: heap array,
      $is_max$: if $a$ is a max heap)
    {Let $n$ be the length of the heap array after insertion}
    $a_n$ := $v$
    $i$ := $n$
    while $i$ > 1
      if $is_max$ is false and $a_{i/2} \le a_i$
        {The heap array now satisfies the condition to be a min heap}
      else if $is_max$ is true and $a_{i/2} \ge a_i$
        {The heap array now satisfies the condition to be a max heap}
      swap $a_{i/2}$ and $a_i$
      $i$ := $i/2$
    {Insertion ends}

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$ during this insertion will be false; otherwise if $b_i$ equals to '1', then $is\_max$ 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'}$.

Sample Input

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

Sample Output



We now explain the first sample test case.

$i$ $v_i$ $b_i$ "Heap" Array after Insertion
1 2 0 {2}
2 3 1 {3, 2}
3 1 0 {1, 2, 3}
4 4 1 {4, 1, 3, 2}

Author: WENG, Caizhi
Source: The 10th Shandong Provincial Collegiate Programming Contest
Submit    Status