题目描述

我们定义数组的LEX是不属于这个数组的最小非负整数。示例：

对于数组$[0，0，1，0，2]$，LEX等于$3$，因为数字$0,1$和$2$出现在数组中，$3$是数组中未出现的最小非负整数；

对于数组$[1，2，3，4]$，LEX等于$0$，因为$0$是数组中未呈现的最小非负整数；

对于数组$[0，1，4，3]$，LEX等于$2$，因为$2$是数组中未出现的最小非负整数。

现在给您一个空数组 a = []（换句话说，一个零长度数组）。和一个正整数$x$。

还将向您提供$q$个操作。在每次操作中，我们会往数组里加入一个数，数组长度增加$1$。

然后，您可以选择任意一个元素$a_i$, 并对 $a_i$执行任意次$a_i = a_i - x$ 或者$a_i = a_i + x$操作，唯一的限制是$a_i$不能变成负数。

现在让您尽可能使每次操作后LEX最大

输入描述

输入的第一行包含两个整数$q,x（1≤q, x≤4⋅10^5）$-查询的数量和x的值。

接下来的$q$行描述查询。第j个查询由一个整数$y（0≤y≤10^9）$，这意味着要将一个元素y添加到数组中。

输出描述

在每次查询后打印初始问题的答案-对于查询j，在第一次j次查询后打印LEX的最大值。请注意，查询是相关的（每次查询后数组都会更改），但查询之间的操作是独立的。

输入输出样例

7 3
0
1
2
2
0
0
10

1
2
3
3
4
4
7

4 3
1
2
1
2

0
0
0
0

提示

在第一个示例中：

在第一次查询之后，数组是$a=[0]$：您不需要执行任何操作，最大可能的LEX是$1$

在第二次查询之后，数组是$a=[0,1]$：您不需要执行任何操作，最大可能的LEX是$2$。

在第三次查询之后，数组是$a=[0,1,2]$：您不需要执行任何操作，最大可能的LEX是$3$。

在第四个查询之后，数组是$a=[0,1,2,2]$：您不需要执行任何操作，最大可能的LEX是$3$（不能通过操作使其更大）。

在第五次查询后，数组为$a=[0,1,2,2,0]$：可以执行$a[4]=a[4]+3=3$。数组变为$a=[0,1,2,2,3]$。现在LEX是可能的最大值，等于$4$。

在第六次查询之后，数组为$a=[0,1,2,2,0,0]$：您可以执行$a[4]=a[4]+3=0+3=3$。数组变为$a=[0,1,2,2,3,0]$。现在LEX是可能的最大值，等于$4$。

在第七次查询之后，数组是$a=[0,1,2,2,0,0,10]$。您可以执行以下操作：

$a[3]=a[3]+3=2+3=5$，

$a[4]=a[4]+3=0+3=3$，

$a[5]=a[5]+3＝0+3＝3$，

$a[5]=a[5]+3=3+3=6$，

$a[6]=a[6]−3=10−3=7$,

$a[6]=a[6]−3=7−3=4$.

结果数组将为$a=[0,1,2,5,3,6,4]$。现在LEX是最大值，等于$7$。