시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

## 문제

After going in the Public Garden, Antonio returns home, where he finds a string of n non-negative integers and a number X. Feeling bored, he decides to invent a game with this array in n steps. Therefore, at each step, Antonio performs 2 actions:

• He determines all the subsequences of the array whose sums are smaller or equal to X and keeps in mind the sum of the sums of such subsequences and their number.
• He circularly permutes the array to the left with one position.

Determine the values kept in mind by Antonio at each step.

## 입력

The first line of the input contains the numbers n and X.

On the second line of this file there are n space-separated elements corresponding to the array.

## 출력

The output has n lines:

The ith line contains two integers separated by a space, the sum of the sums of valid subsequences at step i and their number.

## 제한

• n ≤ 100,000, X ≤ 1,000,000,000
• The elements of the array are between 0 and 106.
• A subsequence of the given array consists of elements found on consecutive positions.

## 예제 입력 1

3 5
1 2 3


## 예제 출력 1

14 5
15 5
13 5


## 힌트

• Stage 1. The sum of the sums of valid subsequences:1 + 2 + 3 + (1 + 2) + (2 + 3)=14 There are 5 valid subsequences. The array becomes 2, 3, 1.
• Stage 2. The sum of the sums of valid subsequences:2 + 3 + 1 + (2 + 3) + (3 + 1)=15 There are 5 valid subsequences. The array becomes 3, 1, 2.
• Stage 3. The sum of the sums of valid subsequences:3 + 1 + 2 + (3 + 1) + (1 + 2)=13 There are 5 valid subsequences. The array becomes 1, 2, 3.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.