配点 : {300} 点
問題文
(1,2,\ldots,N) 的排列在下文中将简称为排列。
順列 P 对于 \mathrm{NextPermutation} (P) 定义如下。 您将获得
- P=(N,N-1,\ldots,2,1) 什么时候 (1,2,\ldots,N-1,N)
- 否则,长度为 N 的所有排列按字典序升序排列时 P 紧随其后的那个
2 个排列 P=(P_1, P_2, \ldots,P_N), Q=(Q_1, Q_2, \ldots, Q_N) 。 对于
P 是 在 (1,2,\ldots, N-1,N) 重复以下操作,直到匹配
- P 该值应乘以 \mathrm{NextPermutation} (P) 在,Q 该值应乘以 \mathrm{NextPermutation} (Q) 。
决赛 Q 。
制約
- 2\leq N\leq 2\times 10^5
- (P_1, P_2, \ldots,P_N),(Q_1, Q_2, \ldots, Q_N) 是 您也可以写 (1,2,\ldots,N) 的排列 给出了
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N P_1 P_2 \ldots P_N Q_1 Q_2 \ldots Q_N
出力
所要求的排列为 Q'=(Q'_1,Q'_2,\ldots,Q'_N) , Q'_1,Q'_2,\ldots,Q'_N 以空格分隔的顺序在一行中输出。
入力例 1
3 2 3 1 3 2 1
出力例 1
2 1 3
通过操作 P,Q 如下所示变化:
- P:(2,3,1)\to (3,1,2)\to (3,2,1)\to (1,2,3)
- Q:(3,2,1)\to (1,2,3)\to (1,3,2)\to (2,1,3)
入力例 2
4 4 2 1 3 2 1 3 4
出力例 2
2 4 1 3
通过操作 P,Q 如下所示变化:
- P:(4,2,1,3)\to (4,2,3,1)\to (4,3,1,2)\to (4,3,2,1)\to(1,2,3,4)
- Q:(2,1,3,4)\to(2,1,4,3)\to(2,3,1,4)\to(2,3,4,1)\to(2,4,1,3)
入力例 3
4 1 2 3 4 1 2 3 4
出力例 3
1 2 3 4
一次操作都不执行。