#6577. 「ICPC World Finals 2019」瓷砖

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: PinkRabbit

题目描述

陶瓷艺术家 Maria 与 João 的一家小型 Azulejo 商店即将在波尔图开业。
Azulejo 是一种在葡萄牙很著名的瓷砖。Maria 与 João 想要让橱窗展示更具吸引力,但由于他们的商店空间有限,他们必须在同一个货架上把他们的瓷砖样品分成两排。
每一块 João 的瓷砖的前面都有一块 Maria 的瓷砖,每块 Maria 的瓷砖的后面都有一块 João 的瓷砖。
这些手工制作的瓷砖有许多不同的尺寸,后排的每块瓷砖需要比前面的瓷砖高,这样路人才能同时看到它们。
为了方便购物者,每行的瓷砖都从左到右按照价格排成非递减序列。只要满足上述的高度限制,价格相同的瓷砖可以被任意排列。

你的任务是找到一种满足这些条件的两排瓷砖的排列,或判断不存在这样的排列。

输入格式

第一行包含一个整数 n 1\le n\le 5\cdot 10^5 ),表示每行瓷砖的个数。
接下来四行,每行包含 n 个整数。前两行描述了后排的瓷砖,后两行描述了前排的瓷砖。
每行的瓷砖都按照输入的顺序从 1 n 标号。
两行中的第一行包含 n 个整数 p_1,\ldots,p_n 1\le p_i\le 10^9 ), p_i 表示该行第 i 个瓷砖的价值。
两行中的第二行包含 n 个整数 h_1,\ldots,h_n 1\le h_i\le 10^9 ), h_i 表示该行第 i 个瓷砖的高度。

输出格式

如果存在合法的排列,输出两行,每行 n 个整数,包含一个 1 n 的排列。
第一行表示后排瓷砖的排列顺序,第二行表示前排瓷砖的排列顺序。
如果有多种方案满足条件,输出任意一种均可通过本题。
如果不存在合法的排列,输出 \texttt{impossible}

样例

样例输入 1

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

样例输出 1

3 2 4 1
4 2 1 3

样例输入 2

2
1 2
2 3
2 8
2 1

样例输出 2

impossible

数据范围与提示

1\le n\le 5\cdot 10^5

1\le p_i,h_i\le 10^9

在不侵犯原题版权的情况下,本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布,注明出处时需指向本题链接。