#M073. 单位蒙日矩阵乘法

    ID: 5702 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-差分转化不变量分析懒标记线段树线段树上二分普通线段树

单位蒙日矩阵乘法

Description

For a permutation aa of order nn, let f(a)f(a) be a (n+1)×(n+1)(n+1)\times (n+1) square matrix, and f(a)i,j=∑i′≥i[ai′<j]f(a)_{i,j}=\sum_{i'\geq i}[a_{i'}<j], all indices are 11-indexed.

For two matrices A,BA, B, we define the distance product A⊗BA\otimes B be $(A\otimes B)_{i,j} = \min_k \left(A_{i,k}+B_{k,j}\right)$.

You are given two permutations a,ba, b of order nn, it can be shown that there exists a unique permutation cc satisfying f(a)⊗f(b)=f(c)f(a)\otimes f(b)=f(c), please compute cc.

Input

The first line contains one positive integer nn.

The rest two lines contain nn positive integers for each line, representing the permutations a,ba,b respectively.

Output

Please output nn integers in one line, representing the permutation cc.

3
1 3 2
2 1 3

2 3 1

Limits And Hints

For 30%30\% of the dataset, it's guaranteed that n≤100n\leq 100.

For 100%100\% of the dataset, it's guaranteed that 1≤n≤5×1051\leq n\leq 5\times 10^5, and a,ba,b are permutations.