给定一个包含 $n$ 个不同正整数的序列 $[a_1, a_2, \dots, a_n]$ 和一个正整数 $k$。

定义 $z$ 被 $(x, y)$ 包含，当且仅当 $\min(x, y) < z < \max(x, y)$。

现在，对于每个 $1 \leq m \leq n$：

• 令 $b = [a_1, a_2, \dots, a_m]$。
• 你需要将 $b$ 划分为若干个连续的段。
  • 在每一段中，你选择两个元素（可以相同）。
  • 假设在某一段中选择的两个元素为 $u$ 和 $v$。
    • 如果该段中至少有 $k$ 个元素不被 $(u, v)$ 包含，则该段可以获得 $(u-v)^2$ 的收益；
    • 否则，该段只能获得 $0$ 的收益。
• 你需要确定在最优策略下，可以获得的最大总收益。

输入格式

第一行包含两个正整数 $n$ 和 $k$。

第二行包含 $n$ 个不同的正整数 $a_1, a_2, \dots, a_n$。

输出格式

输出一行，包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 表示 $m=i$ 时的答案。

样例

样例输入 1

6 2
9 8 2 4 3 5

样例输出 1

0 1 49 49 50 53

样例输入 2

20 3
6 15 3 18 1 12 2 16 8 9 10 14 20 11 17 19 13 5 7 4

样例输出 2

0 0 81 144 225 225 337 340 340 386 386 386 468 468 468 514 514 612 612 664

子任务

对于所有数据，保证 $1 \leq n \leq 10^5,\ 2 \leq k \leq 20,\ 1 \leq a_i \leq 10^7$，且 $a$ 中的所有元素互不相同。

子任务 1 (8 分)

$n \leq 1\,000$

子任务 2 (21 分)

$k = 2$

子任务 3 (22 分)

$k \leq 3$

子任务 4 (20 分)

$k \leq 5$

子任务 5 (13 分)

$k \leq 8$

子任务 6 (16 分)

无附加限制。