Ваш друг Иван попросил вас помочь упорядочить его рабочий стол. Рабочий стол может быть представлен как прямоугольная матрица размера \(n \times m\), состоящая из символов '.' (пустая клетка рабочего стола) и '*' (иконка).
Рабочий стол называется хорошим, если все его иконки находятся на каком-то префиксе столбцов и, возможно, префиксе следующего столбца (и не существует иконок за пределами данной фигуры). Другими словами, какое-то количество первых столбцов будет заполнено иконками, а также, возможно, какое-то количество первых клеток следующего (после последнего полного столбца) столбца будет также заполнено иконками (и все иконки на рабочем столе будут принадлежать этой фигуре). Это выглядит довольно похоже на расположение иконок на рабочем столе в реальной жизни.
За один ход вы можете взять одну иконку и передвинуть ее в любую пустую клетку рабочего стола.
Иван любит добавлять иконки на свой рабочий стол, а также удалять их, поэтому он просит вас ответить на \(q\) запросов: чему равно минимальное количество ходов, необходимое для того, чтобы сделать рабочий стол хорошим после добавления/удаления одной иконки?
Заметьте, что запросы остаются навсегда и меняют состояние рабочего стола.
Выходные данные
Выведите \(q\) целых чисел. \(i\)-е из них должно быть равно минимальному количеству ходов, необходимому для того, чтобы сделать рабочий стол хорошим после применения первых \(i\) запросов.