JOI 是一个正在玩绳子的小宝宝。绳子的长度为 $N$，它被放置在一条从左到右的直线上。 绳子由 $N$ 根绳段组成。这些绳段连接成一条直线。每根绳段的长度为 $1$，厚度为 $1$。 绳子总共使用了 $M$ 种颜色。从左往右数第 $i$ 根绳段的颜色为 $C_i$ ($1 \le C_i \le M$)。
JOI 正在缩短绳子。JOI 重复执行以下操作，直到绳子的长度变为 $2$。 设绳子的长度为 $L$。选择一个整数 $j$ ($1 \le j < L$)。通过合并绳段来缩短绳子，使得绳子上从左往右长度为 $j$ 的点成为最左端。更具体地说，执行以下操作： 如果 $j \le L/2$，对于每个 $i$ ($1 \le i \le j$)，将从左往右第 $i$ 根绳段与从左往右第 $(2j - i + 1)$ 根绳段合并。通过此过程，绳子的最右端点保持为最右端点。绳子的长度变为 $L - j$。 如果 $j > L/2$，对于每个 $i$ ($2j - L + 1 \le i \le j$)，将从左往右第 $i$ 根绳段与从左往右第 $(2j - i + 1)$ 根绳段合并。通过此过程，绳子的最左端点变为最右端点。绳子的长度变为 $j$。 如果一根绳段与另一根绳段合并，则两根绳段的颜色必须相同。我们可以在合并前改变绳段的颜色。改变一根绳段颜色的代价等于它的厚度。调整两根绳段的颜色后，将它们合并为一根绳段；其厚度等于两根绳段厚度之和。
JOI 想要最小化将绳子缩短至长度 $2$ 的总操作代价。对于每种颜色，JOI 想要计算出使最终长度为 $2$ 的绳子包含该颜色绳段的最小总操作代价。
你的任务是代替 JOI 解决这个问题。
输入格式
从标准输入读取以下数据。 第一行包含两个空格分隔的整数 $N, M$。这意味着绳子由 $N$ 根绳段组成，绳子使用了 $M$ 种颜色。 第二行包含 $N$ 个空格分隔的整数 $C_1, C_2, \dots, C_N$。这意味着从左往右第 $i$ 根绳段的颜色为 $C_i$ ($1 \le C_i \le M$)。
输出格式
向标准输出写入 $M$ 行。第 $c$ 行 ($1 \le c \le M$) 包含使最终长度为 $2$ 的绳子包含颜色为 $c$ 的绳段的最小总操作代价。
数据范围
所有输入数据满足以下条件： $2 \le N \le 1\,000\,000$。 $1 \le M \le N$。 $1 \le C_i \le M$ ($1 \le i \le N$)。 对于每个 $1 \le c \le M$，至少存在一个整数 $i$ 使得 $C_i = c$。
子任务
子任务 1 [15 分]
满足以下条件： $N \le 15$。 $M \le 10$。
子任务 2 [30 分]
满足以下条件： $N \le 100\,000$。 $M \le 10$。
子任务 3 [10 分]
满足以下条件： $N \le 100\,000$。 $M \le 500$。
子任务 4 [25 分]
- $M \le 5\,000$。
子任务 5 [20 分]
没有额外限制。
样例
样例输入 1
5 3 1 2 3 3 2
样例输出 1
2 1 1
说明 1
通过以下操作，我们可以缩短绳子，使得最终长度为 $2$ 的绳子包含颜色为 $1$ 的绳段。总代价为 $2$。 将从左往右第 $2$ 根绳段的颜色改为 $1$。缩短绳子，使得从左往右长度为 $1$ 的点成为最左端。绳段颜色变为 $1, 3, 3, 2$。绳段厚度变为 $2, 1, 1, 1$。 将从左往右第 $4$ 根绳段的颜色改为 $1$。缩短绳子，使得从左往右长度为 $2$ 的点成为最左端。绳段颜色变为 $3, 1$。绳段厚度变为 $2, 3$。
通过以下操作，我们可以缩短绳子，使得最终长度为 $2$ 的绳子包含颜色为 $2, 3$ 的绳段。总代价为 $1$。 缩短绳子，使得从左往右长度为 $3$ 的点成为最左端。绳段颜色变为 $3, 2, 1$。绳段厚度变为 $2, 2, 1$。 将从左往右第 $3$ 根绳段的颜色改为 $2$。缩短绳子，使得从左往右长度为 $2$ 的点成为最左端。绳段颜色变为 $2, 3$。绳段厚度变为 $3, 2$。
样例输入 2
7 3 1 2 2 1 3 3 3
样例输出 2
2 2 2
说明 2
通过以下操作，我们可以缩短绳子，使得最终长度为 $2$ 的绳子包含颜色为 $1$ 的绳段。总代价为 $2$。 缩短绳子，使得从左往右长度为 $2$ 的点成为最左端。 将最左端的绳段颜色改为 $1$。缩短绳子，使得从左往右长度为 $1$ 的点成为最左端。注意，改变颜色的代价为 $2$，因为该绳段的厚度为 $2$。 缩短绳子，使得从左往右长度为 $3$ 的点成为最左端。 缩短绳子，使得从左往右长度为 $1$ 的点成为最左端。
样例输入 3
10 3 2 2 1 1 3 3 2 1 1 2
样例输出 3
3 3 4
说明 3
在缩短绳子之前，我们可以改变若干绳段的颜色。