Problem Description

It is time to eat again, and Big Eater is having trouble deciding what to eat.

There are $n$ ingredients, each with a certain weight. Big Eater can split these $n$ ingredients into any number of contiguous segments, and then pair each segment with a staple food of weight $L$. The disharmony of a segment is defined as the square of (the sum of ingredient weights in this segment minus the weight of the staple food, which is $L$). The disharmony of a meal is the sum of the disharmony values of all segments.

Do not worry about how much food there is, because Code (pinyin: mou Code) is a Big Eater, so no matter how much you make, he can finish it.

Next, Code challenges you to answer the minimum and second minimum disharmony of the meal made from the first $i$ dishes. If you answer correctly, you will get the chance to share this meal with him.

When two different splitting methods produce the same minimum disharmony, output the two minimum disharmony values. That is, the output is not necessarily the strictly second minimum disharmony.

Input Format

The first line contains two positive integers $n$ and $L$, meaning there are $n$ ingredients and the weight of each staple food is $L$.

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

Output Format

Output a total of $n$ lines.

The first line contains one integer, the minimum disharmony for the meal made from the first $1$ dish.

On the $i$-th line, output two integers: the minimum and second minimum disharmony for the meal made from the first $i$ dishes, separated by a space.

5 5
3 6 2 4 8

4
5 16
13 14
6 14
15 23

10 7
4 6 9 1 5 9 5 1 7 1 

9
9 10
13 14
18 19
14 15
18 19
22 23
19 20
19 20
20 21

Hint

Sample 1 Explanation

Line 1: $4=(3-5)^2$
Line 2: $5=(3-5)^2+(6-5)^2$, $16=(3+6-5)^2$
Line 3: $13=(3-5)^2+(6+2-5)^2$, $14=(3-5)^2+(6-5)^2+(2-5)^2$
Line 4: $6=(3-5)^2+(6-5)^2+(2+4-5)^2$, $14=(3-5)^2+(6+2-5)^2+(4-5)^2$
Line 5: $15=(3-5)^2+(6-5)^2+(2+4-5)^2+(8-5)^2$, $23=(3-5)^2+(6+2-5)^2+(4-5)^2+(8-5)^2$

Constraints

This problem uses bundled testdata.

• Subtask 1 (10 pts): $1 \le n \le 10$.
• Subtask 2 (20 pts): $1 \le n \le 200$.
• Subtask 3 (20 pts): $1 \le n \le 3000$.
• Subtask 4 (40 pts): testdata is randomly generated.
• Subtask 5 (10 pts): no special properties.

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $1 \le L, a_i \le 10^4$.

Translated by ChatGPT 5