У вас есть шахматная доска состоящая из \(n\) строк и \(n\) столбцов. Строки пронумерованы снизу вверх от \(1\) до \(n\). Столбцы пронумерованы слева направо от \(1\) до \(n\). Поле находящееся на пересечении \(x\)-го столбца и \(y\)-й строки обозначается как \((x, y)\). Кроме того, \(k\)-й столбец является специальным столбцом.
Изначально доска пуста. Есть \(m\) изменений; \(i\)-е изменение добавляет или удаляет одну пешку. Текущая доска называется хорошей если мы можем переместить все пешки на специальный столбец по следующим правилам:
- Пешку на поле \((x, y)\) можно переместить на поля \((x, y + 1)\), \((x - 1, y + 1)\) или \((x + 1, y + 1)\);
- Вы можете сделать сколько угодно таких ходов;
- Пешки нельзя перемещать за пределы доски;
- В каждом поле не может находится более одной пешки.
Текущая доска может и не быть хорошей. Чтобы исправить это, вы можете добавить дополнительные строки. Эти строки добавляются сверху, т. е. они будут иметь номера \(n+1, n+2, n+3, \dots\).
После каждого из \(m\) изменений выведите одно число — минимальное количество строк, которые нужно добавить, чтобы доска стала хорошей.
Выходные данные
После каждого изменения выведите число — минимальное количество строк, которые нужно добавить, чтобы доска стала хорошей.