#2291. 「THUSC 2016」补退选

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yanQval

题目描述

X 是 T 大的一名老师,每年他都要教授许多学生基础的 C++ 知识。在 T 大,每个学生在每学期的开学前都需要选课,每次选课一共分为三个阶段:预选,正选,补退选;其中「补退选」阶段最忙碌。

在补退选阶段,学生即可以选课,也可以退课。对于X老师来说,在补退选阶段可能发生以下两种事件:

  1. 一个姓名为 S 的学生选了他的课(姓名 S 将出现在 X 的已选课学生名单中)

  2. 一个姓名为 S 的学生退了他的课(姓名 S 将从 X 的已选课学生名单中移除)

同时,X 老师对于有哪些学生选了他的课非常关心,所以他会不定时的查询已选课学生名单,每次查询的格式如下:

最早在哪个事件之后,姓名以 S 为前缀的学生数量超过了 v

X老师看你骨骼惊奇,所以想用这个问题考考你,你当然不会畏惧,所以勇敢的接下了这个任务。

注意1:学生的姓名可能相同,如果有 p 个姓名相同的学生都选了X老师的课,则他们的姓名将出现在X老师的名单上 p 次。

注意2:只有已经选了课的学生才会退课,如果姓名为 S 的学生退课,则在他退课之前X老师的名单上一定有姓名 S

注意3:选课,退课和查询都被定义为「事件」,「事件」的编号从 1 开始

输入格式

第一行包含一个正整数 n ,表示一共发生了 n 个事件。

接下来 n 行,每行描述一个事件;每行第一个正整数 k 表示事件类型:

  1. 如果 k=1 ,表示选课事件,接下来一个字符串 S ,表示一个姓名为 S 的学生选了 X 老师的课

  2. 如果 k=2 ,表示退课事件,接下来一个字符串 S ,表示一个姓名为 S 的学生退了 X 老师的课

  3. 如果 k=3 ,表示查询事件,接下来一个字符串 S 以及三个非负整数 a,b,c .

表示X老师想知道最早在第几个事件之后,姓名以 S 为前缀的学生数量超过了 (a\times |\text{ANS}|+b)\bmod{c} |\text{ANS}| 表示上次查询事件的答案的绝对值,如果当前是第一次查询,则 |\text{ANS}|=0 ;如果任何时刻都没有超过该值,则答案为 -1

注:输入中的所有字符串均只包含小写字母。

输出格式

对于每个查询事件,输出一行表示该查询答案。

样例

样例输入

8
1 jead
1 dec
3 de 0 0 10
1 dec
3 de 0 1 10
2 dec
3 de 0 1 10
3 de 0 2 10

样例输出

2
4
4
-1

数据范围与提示

n\leq 100000, |S| \leq 60 ,输入中的所有字符串只会包含前 10 个小写字母