Pirates

Μια ομάδα ~N~ πειρατών βρήκε ~K~ χρυσά νομίσματα. Πρέπει να αποφασίσουν έναν τρόπο να μοιράσουν τα νομίσματα μεταξύ τους. Συμφώνησαν στους ακόλουθους κανόνες:

Ο παλαιότερος πειρατής προτείνει μια μοιρασιά. (Μπορείτε να υποθέσετε ότι όλες οι ηλικίες των πειρατών είναι διαφορετικές.) Μια μοιρασιά αναθέτει έναν μη αρνητικό ακέραιο αριθμό νομισμάτων σε κάθε πειρατή έτσι ώστε το άθροισμα αυτών των αριθμών να είναι ίσο με ~K~.

Στη συνέχεια, κάθε πειρατής θα ψηφίσει είτε «ναι» είτε «όχι» για την πρόταση. Ο αριθμός των ψήφων «ναι» που απαιτούνται για να περάσει η πρόταση εξαρτάται από τον αριθμό των πειρατών. Εάν υπάρχουν ~X~ πειρατές, τότε απαιτούνται ~V[X]~ ψήφοι «ναι» για να περάσει η πρόταση. Εάν η πρόταση περάσει, τα νομίσματα δίνονται ανάλογα με την προτεινόμενη μοιρασιά και η διαδικασία τελειώνει. Διαφορετικά, ο γηραιότερος πειρατής πετιέται στη θάλασσα και η διαδικασία επαναλαμβάνεται χωρίς αυτόν.

Οι πειρατές ενεργούν σύμφωνα με τους παρακάτω κανόνες. Οι κανόνες δίνονται με σειρά προτεραιότητας. Για παράδειγμα, ο κανόνας ~2~ εφαρμόζεται μόνο για τη διάκριση μεταξύ πολλαπλών επιλογών που είναι βέλτιστες σύμφωνα με τον κανόνα ~1~.

1. Ένας πειρατής θα ενεργήσει για να αποτρέψει τον εαυτό του από το να πεταχτεί στη θάλασσα.

2. Ένας πειρατής θα ενεργήσει για να μεγιστοποιήσει τον αριθμό των νομισμάτων που λαμβάνει.

3. Ένας πειρατής θα ενεργήσει για να μεγιστοποιήσει τον αριθμό των πειρατών που πετάγονται στη θάλασσα (εκτός από τον ίδιο,γιατί ο κανόνας ~1~ έχει προτεραιότητα).

4. Ένας πειρατής θα ενεργήσει για να μεγιστοποιήσει τον αριθμό των νομισμάτων που έλαβε ο γηραιότερος πειρατής. Εάν υπάρχουν ακόμα πολλαπλές επιλογές που ταιριάζουν σε αυτούς τους κανόνες, θα μεγιστοποιήσει το χρυσό που λαμβάνει ο δεύτερος γηραιότερος πειρατής, μετά ο τρίτος γηραιότερος πειρατής κτλ.

Εάν υπάρχουν πολλές επιλογές που είναι βέλτιστες σύμφωνα με αυτούς τους κανόνες, τότε ο πειρατής επιλέγει μία δράση αυθαίρετα. (Μπορείτε να υποθέσετε ότι η απάντηση σε αυτό το πρόβλημα δεν εξαρτάται από την επιλογή του πειρατή σε αυτή την περίπτωση.) Επιπλέον, όλοι οι πειρατές είναι απόλυτα λογικοί και γνωρίζουν όλες τις πληροφορίες που περιέχονται σε αυτή τη δήλωση προβλήματος. Δεν μπορούν να κάνουν συμφωνίες ή συνασπισμούς γιατί δεν εμπιστεύεται ο ένας τον άλλον.

Θα αριθμήσουμε τους πειρατές από το ~1~ έως το ~N~ , όπου αυτοί αριθμούνται από τον μικρότερο (πειρατή ~1~) έως τον μεγαλύτερο (πειρατής ~N~ ).

Αν υπήρχαν μόνο ~i~ πειρατές (όπου ~i = 1, ..., N~), πόσα νομίσματα θα έπαιρνε ο μεγαλύτερος από αυτούς;

Είσοδος

Η πρώτη γραμμή της εισόδου θα είναι ο αριθμός ~N~ (~1 \le N \le 10^6~).

Η δεύτερη γραμμή της εισόδου θα είναι ο ακέραιος ~K~ (~1 \le K \le 10^{18}~).

Οι επόμενες ~N~ γραμμές της εισόδου περιέχουν το ~V[i]~ (~1 \le V[i] \le i~) που υποδεικνύει τον αριθμό των ψήφων «ναι» που χρειάζονται για να περάσει μία πρόταση αν παραμένουν ~i~ πειρατές (~i = 1, ..., N~).

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 2\,000~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~max(1, i - 3) \le V[i] \le i~ γιa όλα τα ~i = 1, ..., N~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~K = 10^{18}~.

Έξοδος

Η έξοδος θα πρέπει να αποτελείται από ~N~ ακέραιους, εκτυπωμένοι ένας ανά γραμμή. Η ~i~-οστη γραμμή της εξόδου είναι ο αριθμός από νομίσματα που θα έπαιρνε ο ~i~-οστος πειρατής αν ήταν ο μεγαλύτερος πειρατής. Με άλλα λόγια, αν υπήρχαν μόνο οι πειρατές ~1, ..., i~. Αν ο ~i~-οστος πειρατής πεταχτεί στη θάλασσα, εκτυπώστε -1 στην ~i~-οστη γραμμή.

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

input

5
100
1
1
2
2
3

output

100
100
99
99
98

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

Αν έχουν μείνει ~2~ πειρατές, ο πειρατής ~2~ μπορεί να προτείνει να πάρει αυτός όλο το χρυσό. Μόνο ~1~ ψήφος απαιτείται για να περάσει αυτή η πρόταση, οπότε μπορεί να εγγυηθεί ότι θα περάσει ψηφίζοντας υπέρ.

Αν έχουν μείνει ~3~ πειρατές, ο πειρατής ~3~ χρειάζεται κάποιον άλλον να ψηφίσει για την πρότασή του. Αυτό μπορεί να το εξασφαλίσει δίνοντας ~1~ νόμισμα στον πειρατή ~1~ και ~99~ στον εαυτό του. Ο πειρατής ~1~ ξέρει ότι αν δεν περάσει η πρόταση, δεν θα πάρει τίποτα. Οπότε ένα και μόνο νόμισμα είναι αρκετό για να εξασφαλίσει την ψήφο του.

Αν έχουν μείνει ~4~ πειρατές, ο πειρατής ~4~ δίνει ~1~ χρυσό νόμισμα στον πειρατή ~2~ και ~99~ στον εαυτό του.

Αν έχουν μείνει ~5~ πειρατές, ο πειρατής ~5~ δίνει ~1~ χρυσό νόμισμα στους πειρατές ~1~ και ~3~ και κρατάει ~98~ νομίσματα για τον εαυτό του.

input

5
100
1
2
3
4
4

output

100
-1
-1
-1
100

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

Σε αυτή την περίπτωση, απαιτείται πλήρης συναίνεση για να περάσει μια πρόταση, εκτός αν υπάρχουν ~5~ πειρατές, οπότε απαιτούνται μόνο ~4~ από τις ~5~ ψήφους.

Εάν απαιτείται πλήρης συναίνεση και υπάρχουν ~2~ ή περισσότεροι πειρατές, ο νεότερος πειρατής θα ψηφίσει ενάντια στην πρόταση να μεγιστοποιήσουν τα νομίσματά τους και επίσης να πετάξουν τους περισσότερους πειρατές στη θάλασσα.

Στην περίπτωση που υπάρχουν ~5~ πειρατές, ο γηραιότερος πειρατής θα προτείνει να δώσει στον εαυτό του ~100~ νομίσματα. Όλοι εκτός από τον νεότερο πειρατή θα ψηφίσουν «ναι», γιατί αν αυτή η πρόταση δεν περάσει, ο νεότερος πειρατής θα τους πετάξει όλους στη θάλασσα και μετά θα πάρει τα νομίσματα για τον εαυτό του όταν έχει μείνει μόνο αυτός. Εφόσον οι πειρατές δεν θέλουν να πεταχτούν στη θάλασσα, θα ψηφίσουν «ναι», ακόμη και αν και ο γηραιότερος πειρατής δεν θα τους προσφέρει τίποτα.

input

4
100
1
1
2
3

output

100
100
99
97

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

Οι πρώτες τρεις περιπτώσεις εξηγήθηκαν στο παράδειγμα ~1~.

Όταν υπάρχουν ~4~ πειρατές, ο μεγαλύτερος πειρατής χρειάζεται ~3~ ψήφους. Θα δώσει ~2~ νομίσματα στον νεαρότερο πειρατή και ~1~ νόμισμα στον δεύτερο μικρότερο πειρατή, κρατώντας τα υπόλοιπα για τον εαυτό του.

input

4
2
1
1
2
3

output

2
2
1
-1

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

Η κατάσταση είναι η ίδια όπως στο παράδειγμα ~3~, αλλά τώρα υπάρχουν μόνο ~2~ νομίσματα. Με ~1~, ~2~ ή ~3~ πειρατές, έχουμε τις ίδιες καταστάσεις όπως στο παράδειγμα ~3~.

Με ~4~ πειρατές, ο μεγαλύτερος πειρατής δεν έχει αρκετά νομίσματα για να εξασφαλίσει τις ~3~ ψήφους που χρειάζεται, οπότε θα ριχτεί στη θάλασσα.