C3. Бобер и разрешение коллизий
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Умный Бобер из ABBYY имеет множество увлечений. Одно из них — это построение эффективных хеш-таблиц. Одной из самых серьезных проблем в хеш-таблицах является разрешение коллизий. Бобра очень заинтересовала эта проблема и он решил подробно ее исследовать.

Будем считать, что хеш-таблица состоит из h ячеек, пронумерованных от 0 до h - 1. В нее добавляются и из нее удаляются объекты. Каждый объект имеет свой уникальный идентификатор. Кроме этого, каждому объекту соответствует некоторое значение хеш-функции — целое число из отрезка от 0 до h - 1, включительно. Если при добавлении объекта ячейка, соответствующая значению хеш-функции объекта, свободна, то в нее помещается данный объект. В случае же, когда ячейка уже занята другим объектом, возникает коллизия. При удалении объекта из таблицы ячейка, в которую он был помещен, освобождается.

Умный Бобер недавно узнал о методе линейного пробирования для разрешения коллизий. Он заключается в следующем. Пусть значение хеш-функции для добавляемого объекта равно t и ячейка таблицы с номером t уже занята. Тогда мы пытаемся добавить этот элемент в ячейку (t + mmod h. Если и она занята, то в ячейку (t + 2·mmod h, затем в ячейку (t + 3·mmod h и так далее. Заметим, что возможны ситуации, когда новый объект невозможно добавить в таблицу. Во входных данных для этой задачи гарантируется отсутствие таких ситуаций.

Операция a mod b обозначает взятие остатка от деления числа a на число b.

Данная методика сразу же показалась Бобру весьма неоптимальной и он решил оценить её неэффективность. Итак, вам дана последовательность операций добавления и удаления объектов из таблицы. При добавлении нового объекта происходит последовательность обращений к таблице. Каждое обращение к занятой ячейке таблицы будем называть холостым. Другими словами, если в результате алгоритма, описанного выше, объект добавился в ячейку (t + i·mmod h (i ≥ 0), то произошло ровно i холостых обращений.

Требуется для данной последовательности операций добавления в таблицу и удаления из нее посчитать общее число холостых обращений к таблице. Будем считать, что при удалении некоторого объекта из таблицы не происходит холостых обращений. Также будем считать, что таблица перед выполнением операций пуста, то есть в ней нет ни одного объекта.

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

Первая строка входных данных содержит три целых числа h, m и n (1 ≤ m < h), разделенных пробелами, где h — размер хеш-таблицы, m — число, используемое для разрешения коллизий, n — количество операций.

В следующих n строках содержится описание операций. Порядок их выполнения соответствует порядку, в котором они следуют во входном файле. Каждая операция описывается одной строкой. Формат описания операций следующий:

  • «+ id hash»

    Такой формат имеет операция добавления объекта в таблицу. Первый символ «+» (ASCII 43), затем следует единичный пробел, затем идентификатор объекта id (0 ≤ id ≤ 109), затем еще один пробел и значение хеш-функции для данного объекта hash (0 ≤ hash < h). Идентификатор объекта и значение хеш-функции для данного объекта являются целыми числами.

  • «- id»

    Такой формат имеет операция удаления объекта из таблицы. Первый символ «-» (ASCII 45), затем следует единичный пробел, затем идентификатор объекта id (0 ≤ id ≤ 109). Идентификатор объекта — целое число.

Гарантируется, что для всех операций добавления значение идентификатора является уникальным. Также гарантируется корректность исходных данных, то есть объект всегда возможно будет добавить в хеш-таблицу и не будет удалений несуществующих объектов.

Ограничения на входные данные для получения 20 баллов:

  • 1 ≤ h ≤ 5000
  • 1 ≤ n ≤ 5000

Ограничения на входные данные для получения 50 баллов:

  • 1 ≤ h ≤ 5·104
  • 1 ≤ n ≤ 5·104

Ограничения на входные данные для получения 100 баллов:

  • 1 ≤ h ≤ 2·105
  • 1 ≤ n ≤ 2·105
Выходные данные

Выведите одно целое число — суммарное количество холостых обращений к хеш-таблице.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Примеры
Входные данные
10 2 7
+ 11 0
+ 22 2
+ 33 6
+ 44 0
+ 55 0
- 22
+ 66 0
Выходные данные
7
Входные данные
5 1 6
+ 123 0
+ 234 1
+ 345 2
- 234
+ 456 0
+ 567 0
Выходные данные
4