Codeforces Round 368 (Div. 2) |
---|
Закончено |
Недавно в школе Алина узнала о том, что такое персистентные структуры данных: это структуры данных, которые при внесении в них каких-то изменений сохраняют все свои предыдущие состояния и доступ к этим состояниям.
По приходу домой Алина решила придумать свою персистентную структуру данных. Долго раздумывать не пришлось: прямо перед ее кроватью располагается книжный шкаф. Он, по мнению Алины, весьма подходит в качестве персистентной структуры данных.
Шкаф состоит из n полок, на каждой из которых есть ровно m позиций для книг. Полки в шкафу Алина нумерует от 1 до n, а позиции на полках — от 1 до m. Изначально шкаф пуст, то есть на каждой позиции на каждой полке книга отсутствует.
Алина выписала подряд q операций, которые будут друг за другом производиться со шкафом. Каждая из операций может быть одного из четырех типов:
После выполнения каждой операции Алину интересует количество книг в шкафу. Алина учится на отлично, поэтому она без труда нашла искомые количества. Интересно, а у вас получится?
В первой строке содержится три натуральных числа 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
Иллюстрация ко второму примеру из условия.
Название |
---|