Score : $575$ points

问题陈述

给定排列 $P = (P_1, P_2, \ldots, P_N)$ 和 $A = (A_1, A_2, \ldots, A_N)$，它们都是 $(1,2,\ldots,N)$ 的排列。

你可以执行以下操作任意次数，包括零次：

• 同时将所有的 $A_i$ 替换为 $A_{P_i}$。

打印出可以获得的字典序最小的 $A$。

什么是字典序？

对于长度为 $N$ 的序列，$A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_N)$，如果存在一个整数 $i\ (1\leq i\leq N)$ 使得 $A_i < B_i$，并且对于所有 $1\leq j < i$，$A_j = B_j$，则称 $A$ 字典序小于 $B$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given permutations $P = (P_1, P_2, \ldots, P_N)$ and $A = (A_1, A_2, \ldots, A_N)$ of $(1,2,\ldots,N)$.

You can perform the following operation any number of times, possibly zero:

• replace $A_i$ with $A_{P_i}$ simultaneously for all $i=1,2,\ldots,N$.

Print the lexicographically smallest $A$ that can be obtained.

What is lexicographical order?

For sequences of length $N$, $A = (A_1, A_2, \ldots, A_N)$ and $B = (B_1, B_2, \ldots, B_N)$, $A$ is lexicographically smaller than $B$ if and only if:

• there exists an integer $i\ (1\leq i\leq N)$ such that $A_i < B_i$, and $A_j = B_j$ for all $1\leq j < i$.

Constraints

• $1\leq N\leq2\times10^5$
• $1\leq P_i\leq N\ (1\leq i\leq N)$
• $P_i\neq P_j\ (1\leq i<j\leq N)$
• $1\leq A_i\leq N\ (1\leq i\leq N)$
• $A_i\neq A_j\ (1\leq i<j\leq N)$
• All input values are integers.

Input

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

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

$A_1$ $A_2$ $\ldots$ $A_N$

Output

Let $(A_1, A_2, \ldots, A_N)$ be the lexicographically smallest $A$ that can be obtained. Print $A_1, A_2, \ldots, A_N$ in this order, separated by spaces, in one line.

Sample Input 1

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

Sample Output 1

1 4 2 5 3 6

Initially, $A = (4, 3, 1, 6, 2, 5)$.

Repeating the operation yields the following.

• $A = (1, 4, 2, 5, 3, 6)$
• $A = (2, 1, 3, 6, 4, 5)$
• $A = (3, 2, 4, 5, 1, 6)$
• $A = (4, 3, 1, 6, 2, 5)$

After this, $A$ will revert to the original state every four operations.

Therefore, print the lexicographically smallest among these, which is 1 4 2 5 3 6.

Sample Input 2

8
3 5 8 7 2 6 1 4
1 2 3 4 5 6 7 8

Sample Output 2

1 2 3 4 5 6 7 8

You may choose to perform no operations.

Sample Input 3

26
24 14 4 20 15 19 16 11 23 22 12 18 21 3 6 8 26 2 25 7 13 1 5 9 17 10
15 3 10 1 13 19 22 24 20 4 14 23 7 26 25 18 11 6 9 12 2 21 5 16 8 17

Sample Output 3

4 1 22 18 20 13 14 6 15 11 3 26 2 12 5 23 9 10 25 24 7 17 16 21 19 8