You are given a directed graph with $n$ nodes and $n$ edges. Node $i$ has exactly one outgoing edge that leads to node $e_i$. Your task is to find a valid 3-coloring of the graph: the endpoints of each edge should have different colors and you can only use at most 3 colors. It is guaranteed that the graph does not contain any self-loops and it can be proven that a valid coloring always exists when this constraint is met.

Input

The first line contains one integer $n$: the number of nodes.
The second line contains $n$ integers $e_1,\ e_2,\ \dots,\ e_n$: the edges.

Output

Print $n$ integers in the range $[1, 3]$ on a single line. The output should be a valid coloring for the nodes.

Constraints

• $2 \leq n \leq 10^5$
• $1 \leq e_i \leq n$
• $e_i \neq i$

Example 1

Input:

3
2 3 1

Output:

3 2 1

Example 2

Input:

10
3 8 4 5 10 8 5 10 4 6

Output:

1 1 2 1 2 2 1 3 2 1