B - Swap and Maximize 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : {100}

問題文

長さ N の数列 A =(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。

あなたは次の操作を 0 回以上好きな回数行うことができます。

  • 整数 i\ (1 \le i \le N) を選ぶ。 A_iB_i を入れ替える。

数列のスコアを \displaystyle\sum_{i=1}^N \sum_{j=1}^N \mathrm{min} (A_i,B_j) で定めます。

あなたの目標は操作後の数列のスコアを最大化することです。 スコアの最大値を達成するような操作後の数列を一つ出力してください。 そのような数列が複数存在する場合、どれを出力しても構いません。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 入力は全て整数
  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i , B_i \le 10^8
  • ひとつの入力について、含まれるテストケースの N の総和は 2 \times 10^5 を超えない

入力

入力は以下の形式で標準入力から与えられる。

T 
\mathrm{case}_1
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N 
A_1 \ldots A_N
B_1 \ldots B_N

出力

操作後の数列 A',B' であって、スコアの最大値を達成するようなものを次の形式で出力せよ。
答えが複数存在する場合はどれを出力してもかまわない。

A'_1 \ldots A'_N
B'_1 \ldots B'_N

入力例 1

2
3
1 2 3 
4 5 6
2
1 2
2 1

出力例 1

4 2 6
1 5 3
1 2
2 1

1 つ目のケースでは、例えば i=1 とする操作と、 i=3 とする操作を行うことにより、スコアの最大値 22 を達成できます。

2 つ目のケースでは、例えば操作を行わないことにより、スコアの最大値 5 を達成できます。