在 EGOI 农场，员工们负责接收和运输甜瓜。今天早上，农场共收到了 $N$ 个甜瓜。这些甜瓜的编号为 $1$ 到 $N$，其中第 $i$ 个甜瓜（$1 \le i \le N$）的重量为 $A_i$。

Rie 在 EGOI 农场工作，她的任务是将甜瓜装入箱子。现在，农场确定了一个整数 $x$（$1 \le x \le N$）。随后，她将按顺序接收甜瓜 $x, x+1, \dots, N$。她通过重复以下过程将它们装入箱子：

• Rie 会拿出一个空箱子，并不断将甜瓜放入箱中。但是，如果放入下一个甜瓜后箱内甜瓜的总重量会超过 $L$，她就不会将该甜瓜放入当前箱子，而是将当前箱子运走。（在这种情况下，她会将下一个甜瓜放入一个新的箱子中。）

在将甜瓜 $N$ 放入箱子后，她会运走该箱子，工作即告完成。

Rie 希望为所有可能的 $x$ 值做好准备。请编写一个程序，在给定甜瓜信息和箱子最大承重 $L$ 的情况下，计算对于每一个可能的 $x$，她所运走的箱子数量以及最后一个箱子中甜瓜的总重量。

输入格式

从标准输入读取数据。所有输入值均为整数。

$N \ L$ $A_1$ $A_2$ $\vdots$ $A_N$

输出格式

输出 $N$ 行到标准输出。第 $i$ 行（$1 \le i \le N$）对应于 $x = i$ 的情况。该行应包含在 $x = i$ 时运走的箱子数量以及最后一个箱子中甜瓜的总重量，这两个值之间用空格分隔。

数据范围

• $1 \le N \le 200\,000$
• $1 \le L \le 1\,000\,000\,000$
• $1 \le A_i \le L$ ($1 \le i \le N$)

子任务

1. (6 分) $A_1 = A_2 = \dots = A_N$
2. (21 分) $N \le 1\,000$
3. (29 分) 对于每个 $x$，Rie 运走的箱子数量小于或等于 $10$
4. (33 分) 对于每个 $x$，Rie 每个箱子最多放入 $10$ 个甜瓜
5. (11 分) 无附加限制

样例

样例输入 1

7 100
20
80
50
40
20
80
10

样例输出 1

4 10
4 10
3 10
2 90
2 10
1 90
1 10

样例输入 2

6 160
63
63
63
63
63
63

样例输出 2

3 126
3 63
2 126
2 63
1 126
1 63

样例输入 3

5 20
7
10
4
6
8

样例输出 3

2 18
2 8
1 18
1 14
1 8