题目描述

長さ $N$ の狭義単調増加列 $A=(A\ _\ 1,A\ _\ 2,\ldots,A\ _\ N)$ と、長さ $M$ の狭義単調増加列 $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$ が成り立っています。

長さ $N+M$ の狭義単調増加列 $C=(C\ _\ 1,C\ _\ 2,\ldots,C\ _\ {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$

输出格式

答えを $2$ 行で出力せよ。
$1$ 行目には $A\ _\ 1,A\ _\ 2,\ldots,A\ _\ N$ がそれぞれ $C$ では何番目にあるかを空白区切りで出力せよ。
$2$ 行目には $B\ _\ 1,B\ _\ 2,\ldots,B\ _\ M$ がそれぞれ $C$ では何番目にあるかを空白区切りで出力せよ。

题目大意

给定数列 $\{a\}$，$\{b\}$，长度分别为 $n, m$，可得长度 $n+m$ 的数列 $\{c\}$：$c_i=a_i(1\le i\le n), c_i=b_{i-n}(n+1\le i\le n+m)$。求出将 $\{c\}$ 排序后， $\{a\}$ 和 $\{b\}$ 中每个元素在 $\{c\}$ 中的位置。保证 $\forall i\ne j$，均有 $c_i\ne c_j$。$n, m\le 10^5$。

4 3
3 14 15 92
6 53 58

1 3 4 7
2 5 6

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\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$
• 入力はすべて整数

Sample Explanation 1

$C$ は $(3,6,14,15,53,58,92)$ となります。 $A=(3,14,15,92)$ の要素はそれぞれ $1,3,4,7$ 番目にあり、$B=(6,53,58)$ の要素はそれぞれ $2,5,6$ 番目にあります。