合并序列

题目描述

给定长度为 $N$ 和 $M$ 的严格递增序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$ 和 $B=(B _ 1,B _ 2,\ldots,B _ M)$。这里，对任意 $i$ 和 $j$ $(1 \le i \le N,1 \le j \le M)$ 都有 $A _ i \neq B _ j$。

设 $C=(C _ 1,C _ 2,\ldots,C _ {N+M})$ 为通过以下步骤得到的长度为 $N+M$ 的严格递增序列。

令 $C$ 为 $A$ 与 $B$ 的连接。即，对于 $i=1,2,\ldots,N$，$C _ i=A _ i$；对于 $i=N+1,N+2,\ldots,N+M$，$C _ i=B _ {i-N}$。

将 $C$ 按升序排序。

对于 $A _ 1,A _ 2,\ldots,A _ N$ 中的每一个以及 $B _ 1,B _ 2,\ldots,B _ M$ 中的每一个，求出它们在 $C$ 中的位置。 更正式地说，对于每个 $i=1,2,\ldots,N$，求出满足 $C _ k=A _ i$ 的 $k$；对于每个 $j=1,2,\ldots,M$，求出满足 $C _ k=B _ j$ 的 $k$。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$
$B _ 1$ $B _ 2$ $\ldots$ $B _ M$

输出格式

分两行输出答案。

第一行输出 $A _ 1,A _ 2,\ldots,A _ N$ 在 $C$ 中的位置，用空格隔开。

第二行输出 $B _ 1,B _ 2,\ldots,B _ M$ 在 $C$ 中的位置，用空格隔开。

样例

4 3
3 14 15 92
6 53 58

1 3 4 7
2 5 6

$C$ 为 $(3,6,14,15,53,58,92)$。其中第 $1,3,4,7$ 个元素来自 $A=(3,14,15,92)$，第 $2,5,6$ 个元素来自 $B=(6,53,58)$。

4 4
1 2 3 4
100 200 300 400

1 2 3 4
5 6 7 8

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

数据范围

• $1 \le N,M \le 10^5$
• $1 \le A _ 1 \lt A _ 2 \lt \cdots \lt A _ N \le 10^9$
• $1 \le B _ 1 \lt B _ 2 \lt \cdots \lt B _ M \le 10^9$
• 对任意 $i$ 和 $j$，$A _ i \neq B _ j$ $(1 \le i \le N,1 \le j \le M)$
• 输入中的所有值均为整数