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