ABBYY 的智能海狸有很多爱好。其中之一是构建高效的哈希表。哈希表中最严重的问题之一是解决冲突。海狸对这个问题非常感兴趣,他决定详细探究一下。
我们假设哈希表由编号为 0 到 h - 1 的 h 个单元组成。向其中添加或删除对象。每个对象都有自己唯一的标识符。此外,每个对象都有一个相应的哈希值 - 0 到 h - 1 之间的整数(含)。当一个对象被添加到表中时,如果该对象的哈希值对应的单元格是空闲的,那么这个对象就到那里。如果单元格已被另一个对象占据,则会发生碰撞。当从表中删除对象时,它所占用的单元格变为空。
智能海狸最近了解了线性探测来解决碰撞的方法。如下。假设添加的对象的哈希值等于 t 并且表的单元格 t 已被占用。然后我们尝试将此对象添加到单元格 (t + m) mod h 中。如果它也被占用,那么我们尝试 cell (t + 2·m) mod h,然后 cell (t + 3·m) mod h,依此类推。请注意,在某些情况下,新对象可能无法添加到表中。保证该问题的输入不包含此类情况。
运算 a mod b 表示我们取数字 a 除以数字 b 的余数。
对于海狸来说,这种技术立即显得非常不理想,他决定评估其低效率。因此,您将获得一系列操作,每个操作要么向表中添加一个对象,要么从表中删除一个对象。添加新对象时,将执行对表的一系列调用。对占用单元的调用称为虚拟单元。换句话说,如果上述算法的结果是对象被添加到单元 (t + i·m) mod h (i ≥ 0),则恰好执行了 i 次虚拟调用。
您的任务是计算给定的添加和删除序列对表的虚拟调用总数。当从表中删除对象时,假设没有执行任何虚拟调用。在执行操作之前该表是空的,也就是说,最初它不包含任何对象。
输入
输入的第一行包含三个整数 h、m 和 n (1 ≤ m < h),以空格分隔,其中 h 是哈希表的大小,m 是用于解决冲突的数字,n 是操作的数量。
接下来的 n 行包含操作的描述。它们的执行顺序与它们在输入文件中出现的顺序相对应。每个操作都由一行描述。操作说明如下:
- “+ id hash”这是向表中添加对象的操作格式。第一个字符是“+”(ASCII 43),后跟一个空格,然后是对象标识符 id (0 ≤ id ≤ 109),然后是另一个空格,以及给定对象哈希的哈希值 (0 ≤ hash < h)。该对象的对象标识符和哈希值都是整数。
- "-id"这是从表中删除对象的操作格式。第一个字符是“-”(ASCII 45),后跟一个空格,然后是对象标识符 id (0 ≤ id ≤ 109)。对象标识符是一个整数。
保证对于所有加法运算,id 的值是唯一的。它还保证了初始数据是正确的,即总是可以向哈希表添加对象,并且不会删除不存在的对象。
获得 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 说明符。
示例
输入 #1
10 2 7 + 11 0 + 22 2 + 33 6 + 44 0 + 55 0 - 22 + 66 0
输出 #1
7
输入 #2
5 1 6 + 123 0 + 234 1 + 345 2 - 234 + 456 0 + 567 0
输出 #2
4