Напомним, что 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]\).
Выходные данные
Выведите ответ на изначальную задачу после каждого запроса — для запроса \(j\) выведите максимальное значение MEX после первых \(j\) запросов. Стоит заметить, что запроса зависимы (массив меняется после каждого запроса), но операции между запросами независимы.