Escape Plan

Mrs. Worm owns a coal mine that can be represented as a network of $N$ nodes numbered from $1$ to $N$. Node $1$ is the entrance to the mine, and for each other node $i$ there is a one-way tunnel going from a node $P_i$ to $i$, with $P_i < i$. Nodes that don’t have any tunnels coming out of them are called mining shafts.

The Nlogonia government conducted a safety inspection of the mine and noted that, in case of an emergency, workers could be stuck inside the mining shafts, unable to escape. Mrs. Worm will certainly get sued unless she acts quickly!

To avoid this problem, Mrs. Worm decided to dig a set of one-way escape tunnels leading out from the mining shafts. This set must meet the following conditions:

1. Each mining shaft $s$ has exactly one escape tunnel going from $s$ to a node $e(s)$, in such a way that there is a path from $e(s)$ to $s$ using only the original $N-1$ tunnels.

2. Each node has at most one escape tunnel that leads to it.

3. There is a path from each mining shaft to the entrance, if both the original tunnels and the escape tunnels can be used.

Mrs. Worm needs your help! Find a valid set of escape tunnels that saves her from being sued or tell her that it is impossible to do so.

Input

The first line contains an integer $N$ ($2 \leq N \leq 5 \times 10^{5}$) representing the number of nodes in the coal mine. Each node is identified by a distinct integer from $1$ to $N$.

The second line contains $N - 1$ integers ${P_2}, {P_3}, \ldots, {P_N}$ ($1 \leq P_i < i$), representing that there is a tunnel going from node $P_i$ to node $i$.

Output

Output a single line with $N$ integers ${E_1}, {E_2}, \ldots, {E_N}$, such that $E_i=e(i)$ if node $i$ is a mining shaft, and $E_i=0$ otherwise. If there are multiple solutions, output any of them.

If there is no valid set of escape tunnels, output a single line with the character “*” (asterisk) instead.

Examples

Input

2
1

Output

0 1

Input

3
1 1

Output

*

Input

8
1 2 3 4 4 2 7

Output

0 0 0 0 1 3 0 2

Explanation

Nodes 5, 6 and 8 are the mining shafts. The figure below shows four possible sets of escape tunnels for this test case. The first three sets are invalid, each one breaking one of the conditions. The last set is the proposed output e(5) = 1, e(6) = 3 and e(8) = 2, which is valid.