当前没有测试数据。

C - 合并序列

得分：$300$ 分

问题描述

给定两个长度为 $N$ 和 $M$ 的严格递增序列：$A=(A _ 1,A _ 2,\ldots,A _ N)$ 和 $B=(B _ 1,B _ 2,\ldots,B _ M)$。 这里，对于每个 $i$ 和 $j$ $(1\leq i\leq N,1\leq j\leq 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$，找到一个 $k$ 使得 $C _ k=A _ i$，并且对于每个 $j=1,2,\ldots,M$，找到一个 $k$ 使得 $C _ k=B _ j$。

约束

• $1\leq N,M\leq 10^5$
• $1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9$
• $1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9$
• 对于每个 $i$ 和 $j$ $(1\leq i\leq N,1\leq j\leq M)$，有 $A _ i\neq B _ j$。
• 输入中的所有值都是整数。

输入

从标准输入读入输入数据，具体格式如下所示：

$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