Long gone are the days of math homework. Now that the final year of school is beginning, students are expected to do their own independent study of their subjects instead. To help them study, the students will be grouped into study groups.

There are ~N~ students labelled from ~1~ to ~N~, and ~N~ subjects labelled from ~1~ to ~N~. Each student will be allocated to exactly one study group, denoted by a single positive integer. Recently, researchers have discovered that if a student studies subject ~X~ on one day, then it is optimal for that student to study subject ~P_X~ on the following day. Hence, the students have made the following plan: on day ~1~, the ~i~-th student will study subject ~i~. Then, if student ~i~ studied subject ~X~ on day ~D~, they will study subject ~P_X~ on day ~D+1~. This continues indefinitely.

At the end of each day, the students in each study group will meet and share the information they learnt about the subject they studied that day. To reinforce learnt material, on each day, and for each subject, the students who studied that subject on that day should belong to the same study group. Study groups must not change on any day.

As the principal, you wish for there to be as many study groups as possible. To maximise the number of study groups, you have enough influence to make one adjustment plan: you may choose two integers ~A~ and ~B~ ~(1 \le A, B \le N)~ and set ~P_A~ to ~B~.

Can you determine the optimal adjustment to the plan, and an optimal allocation of students to study groups?

If the adjustment to the plan is not optimal, but the allocation of students to study groups is optimal for the chosen plan, you will receive ~30~% of the points.

Constraints

~1 \le N \le 10^6~

~1 \le P_X \le N~

Input Specification

The first line contains a single integer, ~N~.

The second line contains ~N~ space-separated integers, ~P_1, P_2, \dots, P_N~.

Output Specification

On the first line, output two space-separated integers, ~A~ and ~B~, representing the chosen adjustment to the plan. It is possible that ~P_A~ already equals ~B~, in which case the plan is not adjusted.

On the second line, output ~N~ space-separated integers. The ~i~-th integer represents the study group which the ~i~-th student is allocated to. All integers should be between ~1~ and ~N~ (inclusive), and the number of unique integers should be maximised for the chosen plan.

Sample Input

4
2 3 4 3

Sample Output

2 1
1 2 3 4

Explanation

If no adjustment to the plan is made, it can be shown that at most two study groups can be formed, as demonstrated by the table below. Students ~1~ and ~3~ can form one study group, and students ~2~ and ~4~ can form another study group. It can be shown that on every day, for each subject, the students who studied that subject belong to the same study group.

Day	Student ~1~'s subject	Student ~2~'s subject	Student ~3~'s subject	Student ~4~'s subject
~1~	~1~	~2~	~3~	~4~
~2~	~2~	~3~	~4~	~3~
~3~	~3~	~4~	~3~	~4~
~4~	~4~	~3~	~4~	~3~
~5~	~3~	~4~	~3~	~4~
~6~	~4~	~3~	~4~	~3~
~\vdots~	~\vdots~	~\vdots~	~\vdots~	~\vdots~

When the adjustment to plan is made, all four students can be in their own separate study group.