There is a tree that contains $n$ vertices and the tree is rooted at node 1. For every node such as $i^{th}$ node, $a_i$ is written on it. Consider the following code:

b := an array of length n
time := 1

procedure DFS(T, a, v):
    b[time] = a[v]
    time += 1
    label v as visited
    for u in T.neighbors(v) do:
        if not visited[u] do:
            DFS(T, a, u)
        end if
    end for
end procedure

procedure countInversions()
    DFS(T, a, 1)
    return number of inversions in the array b
    /* Number of inversions in the array b is the number of distinct pairs (i, j) such that 1 <= i < j <= n and b[i] > b[j] */
end procedure

You are required to call $countInversions‍$. The return value of the function depends on the order of children attached to vertices. Determine the minimum return value of $countInversions‍$ over all possible ordering of children attached to vertices, print this order.

Input format

• First line: $n$
• Second line: $a_1,\ a_2,\ \ldots,\ a_n$
• Third line: $p_2,\ p_3,\ \ldots,\ p_n$ where $p_i$ is the parent of the vertex $i$ in the tree

Output format

Determine the minimum return value of $countInversions‍$ over all possible ordering of children of vertices and print the order. You are required to print $n$ lines. In the $i^{th}$ line, print the order of children of vertex $i$. If vertex $i$ does not contain any children, then print $0$.

Constraints

$1 \le n \le 10^6\\ 1 \le a_i \le 10^6\\ 1 \le p_i < i$

Scoring

Arrays $a, p$ are generated randomly