시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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.

채점 및 기타 정보

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