题目描述

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$ 个小写字母。