有 $n$ 部电梯参加一场竞速比赛，比赛从第 $0$ 秒开始，地点是一栋有 $m$ 层楼的建筑，楼层编号为 $1$ 到 $m$。

第 $i$ 部电梯将在第 $x_i$ 秒从 $1$ 楼出发，并以每秒 $1$ 层楼的速度上升。此外，除了 $1$ 楼和 $m$ 楼外，每一层楼都有一个按钮。如果按下该按钮，第一个到达该楼层的电梯将停留 $1$ 秒。如果有超过一部电梯同时到达某一层，只有编号最小的电梯被视为第一个到达。目前没有任何按钮被按下，但你可以在比赛开始前按下某些楼层的按钮。注意，比赛开始后你不能再按下任何按钮。

现在你想知道，通过按下按钮，是否能使第 $i$ 部电梯成为第一个到达 $m$ 楼的电梯，如果可以，最少需要按下多少个按钮。如果有超过一部电梯同时到达 $m$ 楼，只有编号最小的电梯被视为第一个到达。

输入格式

第一行包含两个正整数 $n, m$ ($1 \le n \le 5 \cdot 10^5, 2 \le m \le 10^9$)，分别表示电梯的数量和楼层数。

第二行包含 $n$ 个正整数 $x_1, \dots, x_n$ ($1 \le x_i \le 10^9$)，表示各电梯的出发时间。

输出格式

输出 $n$ 行。第 $i$ 行应包含使第 $i$ 部电梯成为第一个到达 $m$ 楼的电梯所需按下的最少按钮数量。如果不可能，则输出 $-1$。

样例

输入 1

6 20
3 8 12 6 9 9

输出 1

0
8
-1
4
13
14