让我们将数字 0, 1, ..., (n - 1) 的两个排列 p 和 q 的和定义为排列 $${\it Perm}((\mathit{Ord}(p)+\mathit{Ord}(q))\bmod n!)$$,其中 Perm(x) 是数字 0, 1, ... 的按字典顺序排列的第 x 个排列, (n - 1)(从零开始计数),Ord(p)是字典顺序中p的排列数。
例如,Perm(0) = (0, 1, ..., n - 2, n - 1),Perm(n! - 1) = (n - 1, n - 2, ..., 1, 0)
Misha 有两种排列,p 和 q。你的任务是找到它们的总和。
排列 a = (a0, a1, ..., an - 1) 被称为按字典顺序小于排列 b = (b0, b1, ..., bn - 1),如果对于某些 k 以下条件成立:a0 = b0, a1 = b1, ..., ak - 1 = bk - 1, ak < bk。
输入
第一行包含一个整数 n (1 ≤ n ≤ 200 000)。
第二行包含 n 个从 0 到 n - 1 的不同整数,用空格分隔,形成排列 p。
第三行包含n个从0到n-1的不同整数,用空格分隔,形成排列q。
输出
打印 n 个从 0 到 n - 1 的不同整数,形成给定排列的总和。用空格分隔数字。
示例
输入 #1
2 0 1 0 1
输出 #1
0 1
输入 #2
2 0 1 1 0
输出 #2
1 0
输入 #3
3 1 2 0 2 1 0
输出 #3
1 0 2
注意
按字典顺序从 0 到 1 的数字排列:(0, 1), (1, 0)。
在第一个样本中 Ord(p) = 0 且 Ord(q) = 0,因此答案为 $$Perm((0+0) \bmod 2) = Perm(0) = (0,1)$$。
在第二个样本中 Ord(p) = 0 且 Ord(q) = 1,因此答案为 $${ \it Perm}((0+1){\bmod {2}})={\it Perm}(1)=(1,0)$$。
按字典顺序从 0 到 2 的数字排列:(0, 1, 2)、(0, 2, 1)、(1, 0, 2)、(1, 2, 0)、(2, 0, 1)、(2, 1, 0)。
在第三个样本中 Ord(p) = 3 且 Ord(q) = 5,因此答案为 $$Perm((3+5) \bmod 6) = Perm(2) = (1,0,2)$$。