题目描述

冒险者工会每天都会迎来一大批寻找组队队友的冒险者。

一个基本的冒险小队需要有如下配置：一个战士、一个弓箭手、一个魔法师。

如果集齐一个冒险小队，队伍就可以出发。因为队伍太长了，因此后来的人会优先和队尾的人组队。

现在给出冒险者来的序列，每当有冒险小队集齐的时候，计算出组队时的三个人中的最长等待时间。

输入格式

第一行一个整数 n（1≤n≤10⁵），表示来的冒险者人数。

接下来 n 行，每行一个字符串 v 和一个整数 t（1≤t≤10⁸），分别代表当前冒险者的职业（warrior 表示战士，archer 表示弓箭手，magician 表示魔法师），以及冒险者的到来的时间（输入顺序按到来先后顺序已排好序）。

输出格式

若干个整数，每个整数占一行。当有冒险小队集齐的时候，计算出组队时的三个人中的最长等待时间。

输入样例 #1

10
magician 682
archer 842
magician 1841
magician 2081
warrior 2575
magician 3269
archer 4009
warrior 6454
warrior 6679
warrior 7370

输出样例 #1

1733
3185

输入样例 #2

7
magician 1
archer 5
magician 12
warrior 22
warrior 35
archer 38
magician 44

输出样例 #2

17
37

输入样例 #3

7
magician 217
archer 220
magician 226
warrior 235
warrior 247
archer 249
magician 254

输出样例 #3

15
32

提示

样例解释

从每一行的长度和题目要求来看，只能组成两个小队。

再根据优先考虑和队尾的人组队，那么在 2575 时间到来的 warrior 职业的冒险者只能选择和 2081 时间到来的 magician 以及 842 时间到来的 warrior 组队。

此时整队的到来时间最大相差为 2575−842=1733，也就是三人中最长的等待时间。

同理，第二队由 3269、4009、6454 三个时间到来的人组成，三人中最长的等待时间为6454−3269=3185。

数据范围

第一行一个整数 n（1≤n≤10⁵），表示来的冒险者人数。

接下来 n 行，每行一个字符串 v 和一个整数 t（1≤t≤10⁸），分别代表当前冒险者的职业（warrior 表示战士，archer 表示弓箭手，magician 表示魔法师），以及冒险者的到来的时间（输入顺序按到来先后顺序已排好序）。