TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5003
  • 题目
  • P5003「THUSC 2016」补退选
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 512m
    问题描述

    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*|\text|+b)\bmod\(,\)|\text|\(表示上次查询事件的答案的绝对值,如果当前是第一次查询,则\)|\text|=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$ 个小写字母