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

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

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

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

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

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