Недавно в школе Алина узнала о том, что такое персистентные структуры данных: это структуры данных, которые при внесении в них каких-то изменений сохраняют все свои предыдущие состояния и доступ к этим состояниям.

По приходу домой Алина решила придумать свою персистентную структуру данных. Долго раздумывать не пришлось: прямо перед ее кроватью располагается книжный шкаф. Он, по мнению Алины, весьма подходит в качестве персистентной структуры данных.

Шкаф состоит из n полок, на каждой из которых есть ровно m позиций для книг. Полки в шкафу Алина нумерует от 1 до n, а позиции на полках — от 1 до m. Изначально шкаф пуст, то есть на каждой позиции на каждой полке книга отсутствует.

Алина выписала подряд q операций, которые будут друг за другом производиться со шкафом. Каждая из операций может быть одного из четырех типов:

• 1 i j — Поставить книгу в шкаф на позицию j на полке i, если ее там нет.
• 2 i j — Убрать книгу из шкафа с позиции j на полке i, если она там есть.
• 3 i — Поменять расположение книг на полке i на противоположное. Это означает, что со всех позиций на полке i, где книга присутствует, книгу следует убрать, а на все позиции на полке i, где книга отсутствует, книгу следует поставить.
• 4 k — Вернуть все книги в шкафу в то состояние, в котором они находились после выполнения k-й операции. В частности, k = 0 означает, что шкаф следует привести в изначальное состояние, то есть убрать книгу с каждой позиции на каждой полке.

После выполнения каждой операции Алину интересует количество книг в шкафу. Алина учится на отлично, поэтому она без труда нашла искомые количества. Интересно, а у вас получится?