「EVOI-RD2」大胃王

题目描述

又到了一日三度的吃饭时间,大胃王开始因为吃什么饭而犯难了。 现有 $n$ 个材料,每个材料有一定的质量。大胃王可以把这 $n$ 个材料分为**连续**的任意段,然后每一段配一段质量为 $L$ 的主食。每一段的不和谐度定义为这段材料的质量和减去该段主食的质量(就是 $L$)的平方。一顿饭的不和谐度为所有段的不和谐度之和。 不用担心饭的多少的问题,因为某Code 是大胃王,所以做多少他都能吃完。 接下来,某Code 向你发起了挑战,要求你回答前 $i$ 道菜所做出的一顿饭的**最小和第二小**不和谐度。如果你回答正确,你将获得与他共享这顿饭菜的机会。 当两种分配方法得出同样最小的不和谐度时,则输出两个最小的不和谐度。即所输出的并非严格第二小不和谐度。

输入输出格式

输入格式


第一行,两个正整数 $n$ 和 $L$,分别表示有 $n$ 个材料和每份主食的质量 $L$。 第二行 $n$ 个整数,第 $i$ 个整数代表第 $i$ 个材料的质量 $a_i$。

输出格式


输出共 $n$ 行。 其中第一行一个整数,为前 $1$ 道菜做出的饭的最小不和谐度。 在第 $i$ 行输出两个整数,为前 $i$ 道菜所做出的一顿饭的**最小和第二小**不和谐度,中间用空格隔开。

输入输出样例

输入样例 #1

5 5
3 6 2 4 8

输出样例 #1

4
5 16
13 14
6 14
15 23

输入样例 #2

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

输出样例 #2

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

说明

**样例 1 解释** 第一行:$4=(3-5)^2$ 第二行:$5=(3-5)^2+(6-5)^2$,$16=(3+6-5)^2$ 第三行:$13=(3-5)^2+(6+2-5)^2$,$14=(3-5)^2+(6-5)^2+(2-5)^2$ 第四行:$6=(3-5)^2+(6-5)^2+(2+4-5)^2$,$14=(3-5)^2+(6+2-5)^2+(4-5)^2$ 第五行:$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$ **【数据规模与约定】** **本题采用捆绑测试。** + 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):数据随机生成。 + Subtask 5 (10 pts):无特殊性质。 对于 $100\%$ 的数据,$1 \le n \le 2 \times 10^5$,$1 \le L,a_i \le 10^4$。