Meal Harmony Challenge

It's mealtime again and the Big Eater is having trouble deciding what to eat. You are given n ingredients, each having a certain mass. The Big Eater can divide these n ingredients into arbitrarily many continuous segments. For each segment, a staple with a fixed mass L is paired with the segment. The dish unharmony for a segment is defined as \[ \Big(\sum_{i \in \text{segment}} a_i - L\Big)^2, \] and the total unharmony of the meal is the sum of the unharmony over all segments.

Now, Challenge from Code: For each i from 1 to n (i.e. considering the first i ingredients), find the minimum and the second minimum possible total unharmony achievable by partitioning them into continuous segments. Note that if two different segmentation methods yield the same minimum unharmony, then output the same value for both the minimum and the second minimum.

inputFormat

The first line contains two integers n and L (1 ≤ n ≤ 10³ or more, depending on the test data) separated by a space.

The second line contains n integers, where the i-th integer represents the mass of the i-th ingredient.

outputFormat

Output n lines. The i-th line should contain two non-negative integers separated by a space representing the minimum unharmony and the second minimum unharmony achievable for the first i ingredients.

sample

3 10
9 10 11

1 1
1 1
2 122