Notes: For participants in the Prime Contest, please note that partial scores do not count as a solved problem during the contest. You must achieve a full score (100 points) for the problem to be considered solved.

You are given a sequence of $n$ distinct positive integers $[a_1, a_2, \dots, a_n]$ and a positive integer $k$.

Define that $z$ is contained by $(x, y)$ if and only if $\min(x, y) < z < \max(x, y)$.

Now, for each $1 \leq m \leq n$:

• Let $b = [a_1, a_2, \dots, a_m]$.
• You need to partition $b$ into several consecutive segments.
  • In each segment, you select two elements (which can be the same)
  • Suppose the two chosen elements in a segment are $u$ and $v$.
    • If there are at least $k$ elements in the segment that are not contained by $(u, v)$, then you can obtain a gain of $(u-v)^2$ for that segment;
    • otherwise, you can only obtain a gain of $0$ for that segment.
• You need to determine, under the optimal strategy, the maximum total gain you can achieve.

Input

The first line contains two positive integers $n$ ($1 \le n \le 10^5$) and $k$ ($2 \le k \le 20$).

The second line contains $n$ distinct positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$). All elements of $a$ are distinct.

Output

Output one line containing $n$ integers $c_1, c_2, \dots, c_n$, where $c_i$ represents the answer for $m=i$.

Sample 1

Input

6 2
9 8 2 4 3 5

Output

0 1 49 49 50 53

Sample 2

Input

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

Output

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

Scoring

Notes: For participants in the Prime Contest, please note that partial scores do not count as a solved problem during the contest. You must achieve a full score (100 points) for the problem to be considered solved.

For all data, it is guaranteed that $1 \leq n \leq 10^5,\ 2 \leq k \leq 20,\ 1 \leq a_i \leq 10^7$, and all elements of $a$ are distinct.

Subtask 1 (8 points)

$n \leq 1\,000$

Subtask 2 (21 points)

$k = 2$

Subtask 3 (22 points)

$k \leq 3$

Subtask 4 (20 points)

$k \leq 5$

Subtask 5 (13 points)

$k \leq 8$

Subtask 6 (16 points)

No additional constraints.