题目描述

又到了一日三度的吃饭时间，大胃王开始因为吃什么饭而犯难了。

现有 $n$ 个材料，每个材料有一定的质量。大胃王可以把这 $n$ 个材料分为连续的任意段，然后每一段配一段质量为 $L$ 的主食。每一段的不和谐度定义为这段材料的质量和减去该段主食的质量（就是 $L$）的平方。一顿饭的不和谐度为所有段的不和谐度之和。

不用担心饭的多少的问题，因为某Code 是大胃王，所以做多少他都能吃完。

接下来，某Code 向你发起了挑战，要求你回答前 $i$ 道菜所做出的一顿饭的最小和第二小不和谐度。如果你回答正确，你将获得与他共享这顿饭菜的机会。

当两种分配方法得出同样最小的不和谐度时，则输出两个最小的不和谐度。即所输出的并非严格第二小不和谐度。

输入格式

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

第二行 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个材料的质量 $a_i$。

输出格式

输出共 $n$ 行。

其中第一行一个整数，为前 $1$ 道菜做出的饭的最小不和谐度。

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

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

提示

样例 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$。