Comeback

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.

• 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.