我们称一个长度为 $2K$ 的序列是有趣的，当且仅当其前 $K$ 个元素的和与后 $K$ 个元素的和都不大于 $S$。

给定一个长度为 $N$ 的序列 $A$。对于每个元素，输出以该元素开头的最长有趣连续子序列的长度。

输入格式

第一行包含两个整数 $N$ 和 $S$（$2 \le N \le 100\,000$，$1 \le S \le 2 \times 10^9$）。

接下来的 $N$ 行，每行包含一个正整数，依次表示序列 $A$ 的元素。这些整数均为正数，且它们的总和不超过 $2 \times 10^9$。

输出格式

输出共 $N$ 行。第 $i$ 行包含一个整数，表示以第 $i$ 个元素开头的最长有趣连续子序列的长度。如果该位置不存在有趣的连续子序列，则输出 $0$。

样例

输入样例 1

5 10000
1
1
1
1
1

输出样例 1

4
4
2
2
0

输入样例 2

5 9
1
1
10
1
9

输出样例 2

2
0
0
2
0

输入样例 3

8 3
1
1
1
1
1
1
1
1

输出样例 3

6
6
6
4
4
2
2
0