На прямій дорозі довжиною x спочатку є лише два світлофори: у точці \(0\) у точці \(x\) Потім по одному встановлюються ще n світлофорів. Після встановлення кожного нового світлофора необхідно визначити довжину найбільшої ділянки дороги між сусідніми світлофорами.

Input Specification

Перший рядок містить два числа \(n\) та \(x\), де \(x\) --- довжина дороги; \(n\) --- кількість нових світлофорів. Другий рядок містить \(n\) цілих чисел \(p_1, p_2, \ldots, p_n\), де \(p_i\) --- позиція нового світлофора(усі різні). \(\\1 \leq n \leq 2 \cdot 10^5\\\) \(2 \leq x \leq 10^9\\\) \(1 \leq p_i \leq x\\\)

Output Specification

Після кожного встановлення світлофора виведіть максимальну довжину відрізка між сусідніми світлофорами.

Sample Input 1

8 3
3 6 2

Sample Output 1

5 3 3

Sample Input 2

12 5
7 2 1 6 10

Sample Output 2

7 5 5 5 4