Недавно в школе Алина узнала о том, что такое персистентные структуры данных: это структуры данных, которые при внесении в них каких-то изменений сохраняют все свои предыдущие состояния и доступ к этим состояниям.
По приходу домой Алина решила придумать свою персистентную структуру данных. Долго раздумывать не пришлось: прямо перед ее кроватью располагается книжный шкаф. Он, по мнению Алины, весьма подходит в качестве персистентной структуры данных.
Шкаф состоит из 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 означает, что шкаф следует привести в изначальное состояние, то есть убрать книгу с каждой позиции на каждой полке.
После выполнения каждой операции Алину интересует количество книг в шкафу. Алина учится на отлично, поэтому она без труда нашла искомые количества. Интересно, а у вас получится?