D. Максимизация MEX
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Напомним, что MEX массива — это минимальное неотрицательное целое число, которое не представлено в массиве. Примеры:

  • для массива $$$[0, 0, 1, 0, 2]$$$ MEX равен $$$3$$$, потому что числа $$$0, 1$$$ и $$$2$$$ представлены в массиве, а $$$3$$$ является минимальным неотрицательным целым числом, не представленным в массиве;
  • для массива $$$[1, 2, 3, 4]$$$ MEX равен $$$0$$$, потому что $$$0$$$ является минимальным неотрицательным целым числом, не представленным в массиве;
  • для массива $$$[0, 1, 4, 3]$$$ MEX равен $$$2$$$, потому что $$$2$$$ является минимальным неотрицательным целым числом, не представленным в массиве.

Вам задан пустой массив $$$a=[]$$$ (иными словами, массив нулевой длины). Также вам задано положительное целое число $$$x$$$.

Вам дано $$$q$$$ запросов. $$$j$$$-й запрос состоит из одного целого числа $$$y_j$$$, которое означает, что вы должны дописать один элемент $$$y_j$$$ в массив. Длина массива увеличивается на $$$1$$$ после каждого запроса.

За один ход вы можете выбрать любой индекс $$$i$$$ и присвоить $$$a_i := a_i + x$$$ или $$$a_i := a_i - x$$$ (т.е. увеличить или уменьшить любой элемент на $$$x$$$). Единственное ограничение — $$$a_i$$$ не может стать отрицательным. Так как изначально массив пуст, вы можете совершать ходы только после первого запроса.

Вам нужно максимизировать MEX (minimum excluded) массива, применив какое-то количество подобных операций (вы также можете применить несколько таких операций к одному и тому же элементу).

Вам необходимо найти ответ после каждого из $$$q$$$ запросов (то есть $$$j$$$-й ответ соответствует массиву длины $$$j$$$).

Операции отменяются после каждого запроса. То есть массив $$$a$$$ после $$$j$$$-го запроса равен $$$[y_1, y_2, \dots, y_j]$$$.

Входные данные

Первая строка входных данных содержит два целых числа $$$q, x$$$ ($$$1 \le q, x \le 4 \cdot 10^5$$$) — количество запросов и значение числа $$$x$$$.

Следующие $$$q$$$ строк описывают запросы. $$$j$$$-й запрос состоит из целого числа $$$y_j$$$ ($$$0 \le y_j \le 10^9$$$) и означает, что вы должны дописать один элемент $$$y_j$$$ в массив.

Выходные данные

Выведите ответ на изначальную задачу после каждого запроса — для запроса $$$j$$$ выведите максимальное значение MEX после первых $$$j$$$ запросов. Стоит заметить, что запроса зависимы (массив меняется после каждого запроса), но операции между запросами независимы.

Примеры
Входные данные
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]$$$: нет необходимости применять операции, максимально возможный MEX равен $$$1$$$.
  • После второго запроса массив равен $$$a=[0, 1]$$$: нет необходимости применять операции, максимально возможный MEX равен $$$2$$$.
  • После третьего запроса массив равен $$$a=[0, 1, 2]$$$: нет необходимости применять операции, максимально возможный MEX равен $$$3$$$.
  • После четвертого запроса массив равен $$$a=[0, 1, 2, 2]$$$: нет необходимости применять операции, максимально возможный MEX равен $$$3$$$ (вы не можете сделать его больше, применяя операции).
  • После пятого запроса массив равен $$$a=[0, 1, 2, 2, 0]$$$: вы можете совершить операцию $$$a[4] := a[4] + 3 = 3$$$. Массив изменится и станет равен $$$a=[0, 1, 2, 2, 3]$$$. Теперь MEX является максимально возможным и равен $$$4$$$.
  • После шестого запроса массив равен $$$a=[0, 1, 2, 2, 0, 0]$$$: вы можете совершить операцию $$$a[4] := a[4] + 3 = 0 + 3 = 3$$$. Массив изменится и станет равен $$$a=[0, 1, 2, 2, 3, 0]$$$. Теперь MEX является максимально возможным и равен $$$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]$$$. Теперь MEX является максимально возможным и равен $$$7$$$.