Lexicographically Smallest Ball Assignment on a Tree

You are given an integer $$n$$ and $$n$$ balls. The value of the $$i$$-th ball is given by $$p_i$$, and it is guaranteed that \(\{p_1, p_2,\dots,p_n\}\) is a permutation of \(\{1,2,\dots,n\}\). There is also a rooted tree with $$n$$ vertices. Each vertex represents a hole that can hold exactly one ball. The root of the tree is vertex 1.

The process of filling the holes with balls is as follows. For each ball from 1 to $$n$$ (in the given order), perform the following steps:

1. Throw the ball into vertex 1.
2. Let the current vertex be \(p\) (initially \(p=1\)).
3. If vertex \(p\) is already filled with some ball, then select a vertex \(x\) and throw the ball into vertex \(x\), and update \(p=x\); you must choose an \(x\) such that \(x\) is a son (child) of \(p\) and at least one vertex in the subtree of \(x\) is not filled.
4. If vertex \(p\) is empty, the ball fills it.

After all the balls have been thrown, let $$a_i$$ denote the value of the ball in the $$i$$-th vertex. Your task is to choose, at every decision point, a valid child in such a way that the final sequence \(\{a_1, a_2, \dots, a_n\}\) is lexicographically smallest.

It is guaranteed that for any two vertices \(x < y\), the depth \(dep_x\) is no more than \(dep_y\). Here, the depth \(dep_i\) is defined as the number of vertices on the path from vertex \(i\) to the root (vertex 1).

Note: In this problem, numbers inside formulas should be formatted using LaTeX. For example, the condition on the permutation is given as \(\{p_1,p_2,\dots,p_n\} = \{1,2,\dots,n\}\).

inputFormat

The first line contains a single integer $$n$$.

The second line contains $$n$$ space‐separated integers \(p_1, p_2, \dots, p_n\), representing the ball values.

The third line contains $$n-1$$ space‐separated integers. The \(i\)-th integer (for \(i=1,2,\dots,n-1\)) indicates the parent of vertex \(i+1\). It is guaranteed that for every vertex \(i+1\), its parent is a vertex with an index smaller than \(i+1\).

outputFormat

Output $$n$$ space‐separated integers \(a_1, a_2, \dots, a_n\) which represent the value of the ball in the corresponding vertex after all balls have been thrown, ensuring that the sequence is lexicographically smallest.

sample

1
1

1