Kevin 有 $n$ 个整数 $a_1, a_2, \dots, a_n$ 排成一个圆圈。也就是说，数字 $a_i$ 和 $a_{i+1}$ ($1 \le i < n$) 是相邻的。数字 $a_1$ 和 $a_n$ 也是相邻的。因此，每个数字都有且仅有两个邻居。

在一分钟内，Kevin 可以将 $a_i$ 设置为它本身及其两个邻居这三个数中的最小值。或者，Kevin 也可以将 $a_i$ 设置为这三个数中的最大值。例如，如果 $a_i = 5$，且 $a_i$ 的两个邻居分别是 $3$ 和 $2$，那么 Kevin 执行最小值操作后，$a_i$ 将变为 $2$。然而，如果他执行最大值操作，$a_i$ 将保持为 $5$。

对于从 $1$ 到 $m$ 的每个 $x$，求出使所有数字都变为 $x$ 所需的最少分钟数，如果无法做到，则输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$)，分别表示圆圈中整数的个数，以及需要求解的整数个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$)，表示圆圈中的整数。

输出格式

输出 $m$ 个整数。第 $i$ 个整数表示使所有数字都变为 $i$ 所需的最少分钟数，如果无法做到，则输出 $-1$。

样例

输入 1

7 5
2 5 1 1 2 3 2

输出 1

5 5 7 -1 6

说明

要使所有数字都变为 $2$，Kevin 至少需要 $5$ 分钟。以下是一种可能的操作序列：

1. 对 $a_6$ 执行最小值操作，它将变为 $2$。
2. 对 $a_4$ 执行最大值操作，它将变为 $2$。
3. 对 $a_3$ 执行最大值操作，它将变为 $5$。
4. 对 $a_2$ 执行最小值操作，它将变为 $2$。
5. 对 $a_3$ 执行最小值操作，它将变为 $2$。