AT_abc294_c [ABC294C] Merge Sequences

[problemUrl]: https://atcoder.jp/contests/abc294/tasks/abc294_c 長さ $ 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 $ では何番目にあるかを空白区切りで出力せよ。

### 制約 - $ 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 $ 番目にあります。