Description

陶艺家 Maria 和 João 正在波尔图开设一家小型的 azulejo 商店。Azulejos 是葡萄牙著名的美丽陶瓷瓷砖。Maria 和 João 想要创建一个吸引人的橱窗展示，但由于店内空间有限，他们必须将瓷砖样品在一个架子上排列成两行。João 的每块瓷砖前面都有 Maria 的一块瓷砖，Maria 的每块瓷砖后面都有 João 的一块瓷砖。这些手工制作的瓷砖有许多不同的尺寸，重要的是后排的每块瓷砖都比前排的瓷砖高，以便路人都能看到。为了方便顾客，每排瓷砖按价格从左到右非递减排列。相同价格的瓷砖可以在满足上述可见性条件的情况下以任何顺序排列。

你的任务是找到满足这些约束条件的瓷砖排列，或者确定不存在这样的排列。

Input Format

输入的第一行包含一个整数 $n$ ($1 \leq n \leq 5 \times 10^5$)，表示每排的瓷砖数量。接下来的四行每行包含 $n$ 个整数；前两行表示后排的瓷砖，后两行表示前排的瓷砖。每排的瓷砖根据输入中的顺序从 $1$ 到 $n$ 编号。每对中的第一行包含 $n$ 个整数 $p_1, \dots , p_n$ ($1 \leq p_i \leq 10^9$ 对于每个 $i$)，其中 $p_i$ 是该排中编号为 $i$ 的瓷砖的价格。每对中的第二行包含 $n$ 个整数 $h_1, \dots , h_n$ ($1 \leq h_i \leq 10^9$ 对于每个 $i$)，其中 $h_i$ 是该排中编号为 $i$ 的瓷砖的高度。

Output Format

如果存在有效的排列，则输出两行 $n$ 个整数，每行由从 $1$ 到 $n$ 的瓷砖编号的一个排列组成。第一行表示后排瓷砖的排列，第二行表示前排瓷砖的排列。如果有多个满足约束的排列对，任何这样的对都将被接受。如果不存在这样的排列，输出 impossible。

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

3 2 4 1
4 2 1 3

2
1 2
2 3
2 8
2 1

impossible

Hint

来源：ICPC 2019 世界总决赛。

题面翻译由 ChatGPT-4o 提供。