트리 뽑아내기

$1$번 정점부터 $N$번 정점까지 $N$개의 정점으로 이루어진 루트 있는 트리가 있다. 루트는 $1$번 정점이고, $i$번 정점의 부모는 $P_i$번 정점이다($2 \le i \le N$). 각 정점은 서로 다른 정수 가중치를 가지며, $i$번 정점의 가중치는 $A_i$이다($1 \le i \le N$). 자식이 없는 정점을 리프 정점이라고 한다.

루트인 $1$번 정점에서 출발하여 자식 중 가중치가 가장 작은 정점으로 이동하는 과정을 리프 정점에 도달할 때까지 반복한다. 이렇게 $1$번 정점에서 시작하여 리프 정점에서 끝나는 경로 $S = \{S_1, \cdots, S_k\}$를 특별한 경로라고 한다.

뽑아내기 연산은 다음과 같다.

• $S_1$번 정점과 $S_2$번 정점의 가중치를 교환한다.
• $S_2$번 정점과 $S_3$번 정점의 가중치를 교환한다.
• $\cdots$
• $S_{k-1}$번 정점과 $S_k$번 정점의 가중치를 교환한다.
• $S_k$번 정점과 그 부모를 잇는 간선을 트리에서 제거한다.

즉, 특별한 경로 위의 각 정점은 경로에서 자신 다음에 오는 정점의 가중치를 받고, 경로 끝의 리프 정점은 트리에서 제거된다.

그림의 첫 번째 트리에서 특별한 경로는 $S = \{1, 3, 4\}$이며, 뽑아내기를 적용하면 두 번째 트리가 된다. 다섯 번째 트리에서 특별한 경로는 $S = \{1\}$이고, 뽑아내기를 적용하면 $1$번 정점이 제거된다.

이와 같이 주어진 트리에 뽑아내기 연산을 $N$번 수행한다. 각 뽑아내기 연산을 수행하기 전에 $1$번 정점에 적혀 있던 가중치의 값을 구하는 프로그램을 작성하라.

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 $N-1$개의 정수 $P_2, \cdots, P_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $N$개의 정수 $A_1, \cdots, A_N$이 공백으로 구분되어 주어진다.

$N$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 뽑아내기 연산을 수행하기 전 $1$번 정점에 적혀 있던 가중치를 출력한다.

• 주어지는 모든 수는 정수이다.
• $2 \le N \le 300\,000$
• $1 \le P_i < i$ ($2 \le i \le N$)
• $1 \le A_i \le N$ ($1 \le i \le N$)
• $A_1, \cdots, A_N$은 서로 다르다.