Birokracija

Ο Mirko έγινε Διευθύνων Σύμβουλος μιας τεράστιας εταιρείας. Αυτή η εταιρεία αποτελείται από ​Ν άτομα, με ετικέτα από το 1 έως το N​ και η Mirko έχει την ετικέτα 1. Η εταιρεία είναι δομημένη έτσι ώστε κάθε υπάλληλος (εκτός από τη Mirko) να έχει ένα αφεντικό και λέμε ότι ο υπάλληλος είναι βοηθός αυτού του αφεντικού. Κάθε αφεντικό μπορεί να έχει πολλούς βοηθούς, αλλά εξακολουθεί να αναφέρει στο αφεντικό του. Αυτό ισχύει για όλους εκτός από τον Mirko, ο οποίος βρίσκεται στην κορυφή της πυραμίδας και δεν έχει αφεντικό, αλλά έχει τους βοηθούς του.

Όταν ο Mirko παίρνει μια εργασία από τους επενδυτές, στη συνέχεια αναθέτει αυτή την εργασία στον βοηθό του με τον ελάχιστο αριθμό. Αυτός ο βοηθός στη συνέχεια αναθέτει την εργασία στον βοηθό του με τον ελάχιστο αριθμό και αυτή η διαδικασία επαναλαμβάνεται μέχρι να δοθεί η εργασία σε ένα άτυχο άτομο χωρίς βοηθό, ο οποίος στη συνέχεια πρέπει να κάνει την εργασία.

Τότε είναι που αρχίζουν τα πραγματικά προβλήματα. Το άτομο που έκανε την εργασία πληρώνεται 1 νόμισμα, το αφεντικό αυτού του ατόμου παίρνει 2 νομίσματα, το αφεντικό αυτού του ατόμου παίρνει 3 νομίσματα και ούτω καθεξής, μέχρι τον Mirko, ο οποίος παίρνει τόσα νομίσματα όσα άτομα υπάρχουν σε αυτήν την αλληλουχία. Μετά από αυτό, ο υπάλληλος που έκανε πραγματικά τη δουλειά συνειδητοποιεί πόσο άδικο είναι το σύστημα και εγκαταλείπει τη δουλειά του λόγω αρχής.

Βέβαια, ο Μίρκο θα έχει μαζέψει αρκετή περιουσία μέχρι τότε, αλλά θέλει να μάθει και πόσα χρήματα κέρδισε ο καθένας από τους εργαζόμενους.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τον θετικό ακέραιο αριθμό \(N (2 \le N \le 2*10^5​)\), τον αριθμό των εργαζομένων (συμπεριλαμβανομένου του Mirko). Η ακόλουθη γραμμή περιέχει ~N-1~ θετικούς ακέραιους αριθμούς \(a_2​, ​a_3​, ​a_4​, ..., ​a_n (1 \le ​a_i < i)\), όπου το ~a_i~ δηλώνει το αφεντικό του υπαλλήλου ~i~

Έξοδος

Πρέπει να βγάλετε μια γραμμή που να αποτελείται από ​N αριθμούς, ο ~i~-οστός αριθμός αντιστοιχεί στο ποσό των χρημάτων που κέρδισε ο υπάλληλος ~i~​.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των συνολικών πόντων, θα ισχύει ~2 \le N \le 5.000~.

Παραδείγματα

input

3
1 1

output

5 1 1

input

5
1 2 2 4

output

13 8 1 3 1

Επεξήγηση του 2ου παραδείγματος:

Ο Mirko αναθέτει την πρώτη εργασία στον υπάλληλο 2, ο οποίος στη συνέχεια την αναθέτει στον υπάλληλο 3, ο οποίος στη συνέχεια το κάνει. Για αυτό, ο υπάλληλος 3 παίρνει 1 κέρμα, ο υπάλληλος 2 παίρνει 2 νομίσματα και ο υπάλληλος 1 (Mirko) παίρνει 3 κέρματα. Στη συνέχεια, ο υπάλληλος 3 αποχωρεί.
Ο Mirko αναθέτει τη δεύτερη εργασία στον υπάλληλο 2, ο οποίος στη συνέχεια την αναθέτει στον υπάλληλο 4 (επειδή ο υπάλληλος 3 παραιτήθηκε), ο οποίος στη συνέχεια την αναθέτει στον υπάλληλο 5, ο οποίος στη συνέχεια το κάνει. Για αυτό, ο υπάλληλος 5 παίρνει 1 κέρμα, ο υπάλληλος 4 παίρνει 2 νομίσματα, ο υπάλληλος 2 παίρνει 3 νομίσματα και ο υπάλληλος 1 παίρνει 4 νομίσματα.Στη συνέχεια, ο υπάλληλος 5 παραιτείται.
Η διαδικασία επαναλαμβάνεται για συνολικά 5 εργασίες. Συνολικά, ο Mirko παίρνει 13 νομίσματα, ο υπάλληλος 2 παίρνει 8, ο υπάλληλος 4 παίρνει 3 και ο υπάλληλος 3 και 5 παίρνουν από 1 κέρμα.