Dvoniz

Λέμε ότι μια ακολουθία ~2 \times K~ στοιχείων είναι ενδιαφέρουσα αν ούτε το άθροισμα των πρώτων ~K~ στοιχείων, ούτε το άθροισμα των τελευταίων ~K~ στοιχείων δεν είναι μεγαλύτερο από το ~S~.

Δίνεται μια ακολουθία ~A~ μήκους ~N~. Για κάθε στοιχείο, εξάγετε το μήκος της μεγαλύτερης ενδιαφέρουσας υποακολουθίας ξεκινώντας από αυτό το στοιχείο.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~N~ και ~S\;(2 \leq N \leq 100\,000,\;1 \leq S \leq 2 \times 10^9)~.

Οι ακόλουθες ~N~ γραμμές περιέχουν την ακολουθία ~A~, έναν ακέραιο ανά γραμμή. Οι ακέραιοι είναι θετικοί και το άθροισμά τους δεν υπερβαίνει το ~2 \times 10^9~.

Έξοδος

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

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

input

5 10000
1
1
1
1
1

output

4
4
2
2
0

input

5 9
1
1
10
1
9

output

2
0
0
2
0

input

8 3
1
1
1
1
1
1
1
1

output

6
6
6
4
4
2
2
0