分数: 300 点
问题陈述
给你严格递增的长度序列 N 和 M: A=(A _ 1,A _ 2,\ldots,A _ N) 和 B=(B _ 1,B _ 2,\ldots,B _ M)。 在这里, A _ i\neq B _ j 对于每个 i 和 j (1\leq i\leq N,1\leq j\leq M).
让 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) 是长度严格递增的序列 N+M 由以下过程产生。
- 让 C 是以下的串联 A 和 B。正式地,让 C _ i=A _ i 为 i=1,2,\ldots,N,和 C _ i=B _ {i-N} 为 i=N+1,N+2,\ldots,N+M.
- 排序 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
- A _ i\neq B _ j 对于每个 i 和 j (1\leq i\leq N,1\leq j\leq M).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A _ 1 A _ 2 \ldots A _ N B _ 1 B _ 2 \ldots B _ M
输出
分两行打印答案。
第一行应包含以下位置 A _ 1,A _ 2,\ldots,A _ N in C,中间有空格。
第二行应包含以下位置 B _ 1,B _ 2,\ldots,B _ M in C,中间有空格。
示例输入 1
4 3 3 14 15 92 6 53 58
示例输出 1
1 3 4 7 2 5 6
C 将是 (3,6,14,15,53,58,92)。 在这里, 1-st, 3-rd, 4-th, 7第一个元素来自 A=(3,14,15,92),以及 2-nd, 5-th, 6第一个元素来自 B=(6,53,58).
示例输入 2
4 4 1 2 3 4 100 200 300 400
示例输出 2
1 2 3 4 5 6 7 8
示例输入 3
8 12 3 4 10 15 17 18 22 30 5 7 11 13 14 16 19 21 23 24 27 28
示例输出 3
1 2 5 9 11 12 15 20 3 4 6 7 8 10 13 14 16 17 18 19