2327. [THUSC 2016] 补退选

【问题描述】

X 是 T 大的一名教师，每年他都会给学生开设《C++编程基础》课程。每个学期开课之前，学生首先需要选择本学期的课程。选课一共分为三个阶段：预选，正选，补退选；其中“补退选”阶段最为忙碌。

在补退选阶段，学生既可以选课，也可以退课。对于 X 老师来说，在补退选阶段可能发生选课和退课两种事件。

选课：一个姓名为$S$的学生选了这门课（姓名$S$将出现在学生名单中）。

退课：一个姓名为$S$的学生退了这门课（姓名$S$将从学生名单中移除）。

同时， X 老师对于有哪些学生选了这门课非常关心，所以他会不定时地查询学生名单。我们把查询也当作一种事件。

查询：给定一个前缀$T$和一个整数$v$，询问最早在哪个事件发生后，姓名以$T$为前缀的学生数量超过了$v$。

X 老师听说你编程能力出色，所以想用这个问题考考你。你当然不会畏惧，所以勇敢地接下了这个任务。请帮助 X 老师完成所有的查询操作。

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

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

注意 3：事件的编号从$1$开始。

【输入格式】

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

接下来$n$行，每行描述一个事件；每行第一个正整数$k$表示事件类型：

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

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

如果$k = 3$，表示查询事件，接下来一个字符串$T$以及三个非负整数$a, b, c$。请你通过给定的$a, b, c$来计算出$v = (a \times |ANS| + b) \% c$，其中$|ANS|$表示上次查询事件的答案的绝对值，如果当前是第1次查询，则$|ANS| = 0$。 X 老师想知道最早在第几个事件之后，姓名以$T$为前缀的学生数量超过了$v$。如果任何时刻都没有超过该值，则答案为$-1$。

注：输入中的所有字符串均只包含英文字母表中前10个小写字母。

【输出格式】

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

【样例输入1】

10
1 abbe
1 bab
3 ba 0 1 10
1 bab
3 ba 0 1 10
1 bab
3 ba 0 2 10
2 bab
3 ba 0 2 10
3 ba 0 3 10

【样例输出1】

-1
4
6
6
-1

【样例输入2】

10
1 bage
1 bab
3 ba 6 1 10
1 bab
3 ba 8 1 4
1 bab
3 ba 7 2 13
2 bab
3 ba 4 2 11
3 ba 1 2 17

【样例输出2】

2
2
6
-1
6

【样例说明】

对于样例1，事件的进程如下表所示：

【数据规模与约定】

【来源】

THUSC2016第二题

数据已是官方数据