D - Adj Swap Lex Max Editorial /

Time Limit: 3 sec / Memory Limit: 2048 MiB

配点 : 2500 点

問題文

(1,2,\ldots,N) の順列 P 及び Q が与えられます． ここで P は辞書順で Q 以下です．

あなたは以下の操作を 0 回以上行うことができます．

  • P の隣接する 2 要素を選んで入れ替える．ただしこの時以下の条件を満たす必要がある．
    • 操作後の P も辞書順で Q 以下である．
    • 入れ替える 2 つの値を (x,y) とするとき，同じ (x,y) が今までの操作で入れ替えられたことがない．ここで x,y の順番は問わない．つまり，(x,y) を一度入れ替えたあとは (x,y) でも (y,x) でも入れ替えることはできない．

最終的な P としてあり得る順列の中で辞書順最大のものを求めてください．

1 つの入力につき，T ケースを解いてください．

制約

  • 1 \leq T \leq 500000
  • 2 \leq N \leq 10^6
  • P は (1,2,\ldots,N) の順列である
  • Q は (1,2,\ldots,N) の順列である
  • P は辞書順で Q 以下である
  • T ケースにわたる N の総和は 10^6 以下
  • 入力はすべて整数

入力

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

T
case_1
case_2
\vdots
case_T

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

N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N

出力

各テストケースについて，答えとなる順列を出力せよ．

入力例 1

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

出力例 1

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

1 つめのテストケースでは，以下のように操作するのが最適です．

  • P=(1,2,3) からスタート
  • (2,3) を入れ替え，P=(1,3,2) になる
  • (1,3) を入れ替え，P=(3,1,2) になる

2 つめのテストケースでは，一度も操作を行わないのが最適です．

Score : 2500 points

Problem Statement

You are given permutations P and Q of (1,2,\ldots,N). Here, P is lexicographically not greater than Q.

You can perform the following operation zero or more times.

  • Choose two adjacent elements of P and swap them. Here, the following conditions must be satisfied.
    • P after the operation is still lexicographically not greater than Q.
    • Let (x,y) be the two values being swapped. The pair (x,y) has never been swapped in previous operations. Here, the order of x,y does not matter. That is, once (x,y) has been swapped, neither (x,y) nor (y,x) can be swapped again.

Find the lexicographically greatest permutation that P can become in the end.

Solve T cases for each input.

Constraints

  • 1 \leq T \leq 500000
  • 2 \leq N \leq 10^6
  • P is a permutation of (1,2,\ldots,N).
  • Q is a permutation of (1,2,\ldots,N).
  • P is lexicographically not greater than Q.
  • The sum of N over the T cases is at most 10^6.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N

Output

For each test case, output the sought permutation.

Sample Input 1

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

Sample Output 1

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

In the first test case, it is optimal to perform operations as follows.

  • Start with P=(1,2,3).
  • Swap (2,3), resulting in P=(1,3,2).
  • Swap (1,3), resulting in P=(3,1,2).

In the second test case, it is optimal to perform no operations at all.