Cho dãy số nguyên dương ~a~ gồm ~n~ phần tử và số nguyên ~k~. Với mỗi vị trí ~i~, hãy tìm chỉ số nhỏ nhất ~j~ sao cho ~j \le i~ và tổng ~a_j + \ldots + a_i \le k~. Nếu không có ~j~ thỏa mãn, in ~-1~.

Dữ liệu vào

Dòng đầu chứa ~n~ và ~k~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Dữ liệu ra

In ~n~ dòng, dòng thứ ~i~ là đáp án cho vị trí ~i~.

Giới hạn

~1 \le n \le 100000~, ~1 \le k \le 10^{9}~, ~1 \le a_i \le 10000~.

V? d?

Input

5 7
1 2 3 4 5

Output

1
1
1
3
5