Обратите внимание, что различие между простой и сложной версиями задачи состоит в том, что в сложной версии недоступные клетки могут снова становиться доступными, а в простой версии не могут. Вы можете взламывать, только если обе версии решены.

Ильдар и Ваня устали постоянно играть в шахматы, поэтому они придумали новую шахматную игру.

Игра происходит на шахматном поле размером $$$2n \times 2m$$$. Это поле имеет $$$2n$$$ строк и $$$2m$$$ столбцов. Клетки этого поля покрашены в черный и белый цвета шахматной раскраской. Более точно, клетка в $$$i$$$-й строке и $$$j$$$-м столбце имеет белый цвет, если $$$i+j$$$ чётно, и чёрный цвет в противном случае.

Игра устроена следующим образом. Ильдар помечает некоторые белые клетки поля как недоступные. После этого он предлагает Ване попробовать решить следующую задачу: может ли он на доступных белых клетках поля расставить $$$n \times m$$$ шахматных королей так, что никакие два выставленных короля не бьют друг друга, то есть не стоят на клетках поля, соседних по стороне или углу.

Конечно, Ильдар планирует сделать игру интересной и предложить Ване несколько сложных комбинаций недоступных клеток. Для этого он попросил у вас помощи. Чтобы перед игрой понять, как лучше всего действовать, он хочет потренироваться. Для этого, он берёт пустое поле и хочет $$$q$$$ раз либо сделать какую-то доступную клетку недоступной, либо сделать какую-то недоступную клетку доступной. После каждого изменения он бы хотел знать, каким будет ответ на задачу для Вани для текущего множества недоступных клеток.

Помогите Ильдару сделать игру интересной! Напишите программу, которая будет отвечать на его запросы.