Melons

Interview

Time limit1sMemory limit1024 MB

Summary

For each start index x, count the boxes needed to pack melons x through N in order under limit L, and report the weight of the last box.

Level: Medium6 of 10
Topics: Greedy, Prefix sum, Two pointers, Dynamic programming
Solved: No attempts yet

Problem

In EGOI Farm, employees receive and ship melons. This morning, $N$ melons arrived. The melons are numbered from 1 to $N$ , and the weight of melon $i$ ( $1 \le i \le N$ ) is $A_i$ .

Rie works at EGOI Farm, packing melons into boxes. An integer $x$ ( $1 \le x \le N$ ) is decided. Then she receives melons $x, x+1, \dots, N$ in this order. She packs them by repeating the following process.

Rie takes an empty box and keeps putting melons into it. If the total weight in the box would exceed $L$ after adding the next melon, she does not put that melon in. She then ships the box. In this case, the next melon goes into a new box.

After melon $N$ is put into a box, she ships that box, and the job ends.

Rie wants to prepare for every possible value of $x$ . Given the melon weights and the maximum box weight $L$ , write a program that computes, for every $x$ , the number of boxes she ships and the total weight of melons in the last box.

Input

The first line contains $N$ and $L$ . Each of the next $N$ lines contains one value: $A_1, A_2, \dots, A_N$ .

N L
A_1
A_2
\vdots
A_N

Output

Print $N$ lines. The $i$ -th line contains, for $x = i$ , the number of shipped boxes and the total weight of melons in the last box, separated by a space.

Constraints

$1 \le N \le 200\,000$
$1 \le L \le 1\,000\,000\,000$ ( $= 10^9$ )
$1 \le A_i \le L$ ( $1 \le i \le N$ )

Examples3

Example 1

Input

Expected output

Example 2

Input

Expected output

Example 3
Input
```
5 20
7
10
4
6
8
```
Expected output
```
2 18
2 8
1 18
1 14
1 8
```