佩奇有一块超级 $CPU$，它有两个超级核⼼ $A$ 和 $B$。

$A$ 核⼼可以同时处理多项任务，每项任务处理时间为 $x$，$B$ 核⼼只能同时处理一项任务，每项任务处理时间为 $y$。

这一天，佩奇接到了 $n$ 项紧急任务，第 $i$ 项紧急任务在 $t_i$ 时刻发出， 且必须在任务发出时进⾏处理。

由于佩奇可以调节 $CPU$ 的 $B$ 核⼼，也就是对于$y$,可以设置为$y=1,2,3……x$

请问：处理完毕所有任务的最早时间是多少？

输入格式

第一行两个整数 $n, x$，表⽰紧急任务数量及 $A$ 核⼼对每项任务的处理时间。第二行 $n$ 个整数 $t_i$，表⽰第 $i$ 个紧急任务发出的时间 $t_i$。

输出格式

共 $x$ 行：第 $i(1\leq i\leq x)$ 行一个整数，表⽰当 $y = i$ 时的答案。

样例输入1

3 3
1 2 3

样例输出1

4
5
6

样例分析1

• $y = 1$ 的时候: $t_1 = 1$ 任务交给核⼼ $A, t_2 = 2, t_3 = 3$ 两个任务交给核⼼ $B$, 结束时刻是 $4$, 这是最早的⼀种完成的⽅案。

• $y = 2$ 的时候: $t_1 = 1, t_3 = 3$ 两个任务交给核⼼ $B, t_2 = 2$ 任务交给核⼼ $A$, 结束时刻是 $5$, 这是最早的⼀种完成的⽅案。

• $y = 3$ 的时候: $t_1 = 1, t_2 = 2$ 两个任务交给核⼼ $A, t_3 = 3$ 任务交给核⼼ $B$, 结束时刻是 $6$, 这是最早的⼀种完成的⽅案。

样例输入2

3 5
1 4 5

样例输出2

6
9
9
9
10

数据范围

对于 $40\\%$ 的数据，$1 \leq n \leq 10^3$

对于 $100\\%$ 的数据，$1 \leq n, x \leq 10^6，0 \leq t_{i−1} \leq t_i \leq 10^9$