Migrated from Lutece 2650 路径规划

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这是发生在花咲川女子学院里两个高一学生之间的一个故事。

户山香澄因为总是在有咲的流星堂练习吉他觉得有些不好意思，因此打算去礼物店给有咲买点礼物送给有咲。店铺的打烊时间是有先后顺序的，香澄想要按照该顺序依次先后访问每个店铺。并且香澄也希望尽早到达每个店铺，以便有尽可能多的时间挑选礼物。城镇里总共有 $p$ 条街道，标号分别为 $0$ 到 $p-1$。第 $i$ 个店铺位于第 $a_i$ 条街道上，香澄最开始在第 $1$ 个店铺，她想知道按照打烊顺序访问剩下的每个店铺赶路所需要的最少的总单位时间。

如果香澄在第 $u$ 条街道上，那么香澄有三种移动方式：

1. 香澄跑到上一条街道上，$u\to (u+p-1)\bmod p$，消耗 $1$ 单位时间；
2. 香澄跑到下一条街道上，$u\to (u+1)\bmod p$，消耗 $1$ 单位时间；
3. 香澄唤醒自己的キラキラドキドキ之魂，发现一条贴满星星贴纸的小路,香澄穿过小路到达一个街道，$u\to \text{inv}(u,p)$，消耗 $2$ 单位时间。当 $u=0$ 时，香澄不能使用这种移动方式。

其中，$\text{inv}(u,p)$ 表示 $u$ 在模 $p$ 意义下的乘法逆元。

Input

第一行输入两个正整数 $n,p$，分别表示香澄要前往的礼物店的数量和城镇街道的数量。 第二行输入 $n$ 个正整数 $a_i$，表示第 $i$ 个要打样的礼物店位于的街道位置。

Output

输出 $n-1$ 行，第 $i$ 行表示从第 $1$ 个礼物店移动到第 $i$ 个礼物店，香澄在赶路上花费的最少的总单位时间。

Samples

2 7
3 5

2

3 17
1 13 1

5
10

Constraints

$2\le n\le 8$ $2\le p\le 10^8+7$ $0\le a_i\le p-1$ $p$ 保证是质数。

Note

忽略香澄到了目的街道后在街道里找礼物店的时间。 若某两个打样时间相邻的店铺位于同一个街道，则香澄不需要消耗时间用来赶路。

Resources

2021 UESTC ICPC Training for String and Search Algorithm