Một dãy độ dài ~2 \times k~ được coi là interesting, nếu tổng ~k~ phần tử đầu tiên nhỏ hơn hoặc bằng ~s~ và tổng ~k~ phần tử tiếp theo nhỏ hơn hoặc bằng ~s~.

Cho dãy ~a~ độ dài ~n~. Với tất cả mọi vị trí ~i~ trong dãy ~a~, bạn cần tìm một dãy interesting dài nhất bắt đầu từ vị trí ~i~.

Yêu cầu: Tìm độ dài dãy interesting dài nhất bắt đầu tại mỗi vị trí ~i~.

Input

• Dòng đầu tiên gồm 2 số nguyên ~n~ và ~s~ (~2 \le n \le 100000, 1 \le s \le 2 \times 10^9~).
• ~n~ dòng sau mỗi dòng ghi 1 số nguyên thể hiện số thứ ~i~ trong dãy ~a~. Các số là nguyên dương và tổng của chúng không vượt quá ~2 \times 10^9~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ thể hiện dãy interesting dài nhất bắt đầu ở vị trí thứ ~i~ trong dãy.

Sample Input 1

5 10000
1
1
1
1
1

Sample Output 1

4
4
2
2
0