Hằng năm ở Wisconsin tụi bò lại tổ chức ngày hội Halloween vào kỳ nghỉ Thu. Chúng sẽ mặc đồ hóa trang và đi xin kẹo nông dân John đã đặt trong N (1 <= N <= 100,000) chuồng bò (để thuận tiện ta đánh số các chuồng bò từ 1 -> N).

Để cho lũ bò chơi vui hơn, ở chuồng i John sẽ cắm 1 biển báo next_i (1 <= next_i <= N) cho biết sau khi xin kẹo ở chuồng i thì bò sẽ phải tiếp tục đi tới chuồng next_i để xin kẹo tiếp.

Bò i sẽ bắt đầu xin kẹo từ chuồng i. Và một con bò sẽ dừng việc xin kẹo nếu nó đi tới 1 chuồng mà nó đã từng đi qua rồi.

Tính xem mỗi con bò sẽ xin được bao nhiêu kẹo, biết rằng ở mỗi chuồng chúng chỉ xin được 1 viên kẹo mà thôi.

Input

• Dòng 1: Một số nguyên duy nhất: N
• Dòng 2..N+1: Dòng i+1 gồm 1 số nguyên duy nhất: next_i

Output

• Dòng 1..N: Dòng i chứa 1 số nguyên là số kẹo mà bò i nhận được

Example

Input
4
1
3
2
3

Output
1
2
2
3