Description

DreamGrid 正在数据结构课上学习堆的插入操作。

在下面的描述中，我们将 $i/2$ 记作满足 $2x \le i$ 的最大整数 $x$。回忆如下内容：

• 一个大小为 $n$ 的堆是一个数组 $a_1, a_2, \dots, a_n$，其满足以下两个条件之一：
  • 对于所有 $2 \le i \le n$，都有 $a_{i/2} \le a_i$。这称为小根堆。
  • 对于所有 $2 \le i \le n$，都有 $a_{i/2} \ge a_i$。这称为大根堆。
• 插入操作可描述为如下伪代码： :::align{center} :::

DreamGrid 准备了一个初始为空的堆数组 $a$ 和 $n$ 个整数 $v_1, v_2, \dots, v_n$。他正准备依次把这 $n$ 个整数插入堆数组，这时手机响了，于是他把这项工作交给室友 BaoBao 去做。

不幸的是，BaoBao 并不理解插入函数参数 $is\_max$ 的意义（不过亲爱的参赛者，你一定已经理解了这个参数的含义），于是他生成了一个长度为 $n$ 的二进制串（只包含 0 和 1 的字符串）$b = b_1b_2\dots b_n$，其中 $b_i$ 表示串中的第 $i$ 个字符，并且他根据这个字符串决定 $is\_max$ 的值。在插入 $v_i$ 时，若 $b_i$ 等于 0，则此次插入中的 $is\_max$ 为假；否则如果 $b_i$ 等于 1，此次插入中的 $is\_max$ 为真。

当 DreamGrid 回来后，发现最终的“堆”数组 $a_1, a_2, \dots, a_n$ 似乎并不是一个有效的堆！给定依次插入的 $n$ 个整数 $v_1, v_2, \dots, v_n$ 以及最终的数组，并已知 BaoBao 是按照顺序插入 $v_1, v_2, \dots, v_n$ 的，请你帮助 DreamGrid 恢复出 BaoBao 生成的二进制串 $b$。

Input Format

有多组测试数据。输入的第一行包含一个整数 $T$，表示测试数据组数。对于每组测试数据：

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示最终数组的大小。

第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$（$1 \le v_i \le 10^9$），表示依次插入的整数。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，是 $v_1, v_2, \dots, v_n$ 的一个排列，表示最终“堆”的数组。

保证所有测试数据中 $n$ 的总和不超过 $10^6$。

Output Format

对于每组测试数据，输出一行一个二进制字符串，表示用于插入的二进制串。如果存在多个合法答案，输出字典序最小的那个。如果不存在这样的二进制串，则输出 Impossible（不含引号）。

回忆：对于长度为 $n$ 的两个二进制串 $s$ 和 $t$，我们称 $s$ 的字典序小于 $t$，当存在整数 $k$ 满足所有下列条件时：

• $1\le k\le n$。
• 对于所有 $1\le i<k$，都有 $s_i=t_i$。
• $s_k=\text{`0' }$ 且 $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

Hint

下面解释第一个样例：

$$\begin{array}{|c|c|c|c|} \hline \textbf{$i$} & \textbf{$v_i$} & \textbf{$b_i$} & \textbf{插入后 “堆” 数组} \\ \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}$$

由 ChatGPT 5 翻译