멜론

EGOI 농장에서 직원들이 멜론을 받아 출하한다. 오늘 아침 $N$개의 멜론이 들어왔다. 멜론에는 1번부터 $N$번까지 번호가 붙어 있고, $i$번 멜론($1 \le i \le N$)의 무게는 $A_i$이다.

리에는 EGOI 농장에서 멜론을 상자에 담는 일을 한다. 정수 $x$($1 \le x \le N$)가 정해지면, 리에는 멜론 $x, x+1, \dots, N$을 이 순서대로 받는다. 그녀는 다음 과정을 반복해서 멜론을 상자에 담는다.

• 리에는 빈 상자를 하나 가져와서 멜론을 계속 넣는다. 다음 멜론을 넣었을 때 상자 안 멜론의 총 무게가 $L$을 넘으면, 그 멜론은 넣지 않는다. 그러고 나서 그녀는 상자를 출하한다. 이 경우 다음 멜론은 새 상자에 넣는다.

멜론 $N$을 상자에 넣고 나서 그 상자를 출하하면 작업이 끝난다.

리에는 가능한 모든 $x$에 대해 미리 준비하고 싶어 한다. 멜론의 무게 정보와 상자의 최대 무게 $L$이 주어질 때, 각 $x$에 대해 리에가 출하하는 상자의 개수와 마지막 상자에 담긴 멜론의 총 무게를 구하는 프로그램을 작성하라.

첫 줄에 $N$과 $L$이 주어진다. 다음 $N$개의 줄에는 $A_1, A_2, \dots, A_N$이 한 줄에 하나씩 주어진다.

N L
A_1
A_2
\vdots
A_N

$N$개의 줄을 출력한다. $i$번째 줄에는 $x = i$일 때 출하하는 상자의 개수와 마지막 상자에 담긴 멜론의 총 무게를 공백으로 구분해 출력한다.

• $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$)