UOJ Logo

NOI.AC

2S 2048MB

#776. 被删除a次的题目

统计

Description

Universal OJ群有非常恐怖的惩罚制度,也就是所谓的删除制度。当一个人违规时,这个人会被“删除”,也就是群名片前面被打上一个“被删除”标记。例如,如果一个ID为“tourist”的人被“删除”,这个人的ID会变成“被删除的tourist”一个人可以被删除多次,一个被删除多次的人也会有对应的标记。

Universal OJ群关于删除的规定如下:

一个人如果连续三次发言都是水群,那么这个人会被删除一次。

一个人如果回答了问题,且问题的人表示感谢,那么这个人会被“复原”一次,复原的意思是如果这个人被删除过,那么他被删除的次数减一,注意删除次数不能为负,也就是说一个没有被删除的人不能用这一次复原抵消下一次删除。

如果一个人参加了一次UOJ的比赛,那么这个人会被“复原”一次。

你得到了一段按时间顺序的记录,每一条记录有两种可能的格式:

"1 x y",表示一条消息记录,表示名字为x的人说了一句话,这句话为y,保证x和y均只包含小写字母。

"2 m $a_1, a_2, \cdots a_m$",表示一条比赛记录,举办了一场UOJ的比赛,有$m$个人参加,参加的人的名字分别为$a_1, a_2, \cdots a_m$,保证每个名字都只包含小写字母。一个人不会在名单中出现两次。

如果一个人参加了比赛,也就是这个人的名字在$a$中,那么这个人会被“复原”一次。

对于第一种情况的判断,你发现大部分的水群都是以“复读”的形式存在,也就是重复同一句消息,于是你决定用以下方法判断:

如果连续三条消息记录的x和y均相同,那么x被删除一次。

对于第二种情况的判断,你的方法是这样,对于某一条消息记录,如果$y = $“thanks”(不包含引号,严格匹配),那么这条记录被称为感谢记录。这个记录之前的上一条消息的发言人会被复原一次。

为了避免特殊情况,数据保证不会有连续超过三条消息记录的发言人是同一个人。任意一条比赛记录的前后第一条消息记录的发言人不同。第一条消息记录不是感谢记录,且任意一条比赛记录之后的第一条消息记录不是感谢记录。每一条感谢记录的前一条消息记录的发言人与感谢记录的发言人不同,前一条消息记录没有造成发言者被删除,且前一条记录不是感谢记录。

假设最开始每个人都没有被删除过,你需要判断最后每个人的被删除次数。

Task

Input

第一行一个数$n$,表示消息记录条数。

接下来$n$行,每行一条记录,格式如题意所述。

Output

如果没有人的删除次数大于0,输出“None”(不包含引号)

否则,输出若干行,按名字的字典顺序对于每个删除次数大于0的人,用一行输出名字和删除次数,用空格隔开。

Sample 1

16
1 dog woof
1 dog woof
1 dog woof
1 cat meow
1 cat meow
1 cat meow
1 bird tweet
1 bird tweet
1 bird tweet
1 fox ring
1 fox ding
1 fox ding
2 3 cat mouse cow
1 ylvis whatdoesthefoxsay
1 bird askthefox
1 ylvis thanks
dog 1

Explanation

最开始名字为“dog”,“cat”和“bird”的人都三连击了,被删除了一次。

虽然“fox”连续发言了三次,但是这三次发言的内容并不全部相同,所以“fox”没有被删除。

“cat”由于参加了一场比赛从而被复原。最后一句话的内容是“thanks”所以是感谢记录,这条记录的前一条消息记录的发言人为“bird”,所以“bird”也被复原了一次,“dog”成了唯一被删除的人。

Sample 2

样例数据下载

Constraint

对于 $50\%$ 的数据,没有比赛记录。

对于 $100\%$ 的数据,$1 \le n \le 1000$,$1 \le m \le 10$,每个名字和发言都为非空的仅包含小写字母的字符串,且名字长度不超过10,发言长度不超过100。

时间限制2s,空间限制2G。