D. Персистентный шкаф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Шкаф состоит из 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 означает, что шкаф следует привести в изначальное состояние, то есть убрать книгу с каждой позиции на каждой полке.

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

Входные данные

В первой строке содержится три натуральных числа n, m и q (1 ≤ n, m ≤ 103, 1 ≤ q ≤ 105) — размеры шкафа и количество операций соответственно.

В следующих q строках содержится описание операций в порядке их выполнения — в i-й из них содержится описание i-й операции в одном из четырех форматов, описанных в условии.

Гарантируется, что номера полок и номера позиций заданы корректно, а во всех операциях четвертого типа число k соответствует одной из операций, выполненных ранее, либо равно 0.

Выходные данные

Для каждой операции выведите в отдельной строке количество книг в шкафу после её выполнения. Ответы выводите в хронологическом порядке.

Примеры
Входные данные
2 3 3
1 1 1
3 2
4 0
Выходные данные
1
4
0
Входные данные
4 2 6
3 2
2 2 2
3 3
3 2
2 2 2
3 2
Выходные данные
2
1
3
3
2
4
Входные данные
2 2 2
3 2
2 2 1
Выходные данные
2
1
Примечание

Иллюстрация ко второму примеру из условия.