小Z发明了一套新的电影评分系统。这套系统有三种操作:发布新电影、对电影评分、以及询问电影评分的排名。具体是这样运作的:如果是发布新电影,并且这部电影的有所主演之前均没有出现过,那么这部新电影的评分为0,否则这部电影的评分为最近一部与该电影至少有一个共同主演的电影的评分;如果是对电影进行评分,那么这部电影的评分就变成之前评分与新的评分的平均数;如果是查询排名,则根据评分输出相应排名。评分最高的为第一名。如果有多部电影分数相同,那么输出最早的一部。电影的评分在0到5之间。
输入的第一行是n,表示操作次数。接下来n行,每一行是以下三种操作之一：
-
Q x:查询当前排名为x的电影ID
-
R ID x actor1 actor2 …· actorx:发布新电影ID,该电影有x个主演分别为 actor1, actor2,…’
-
C ID score:评分操作,表示对电影ID的评分为 score
数据保证每个电影的ID不相同,且每部电影至多不超过5名主演。
1≤ actor1, actor2,··≤10^5
1≤ID≤10^5
对于每一个查询操作,输出相应排名的电影的ID。
10
R 1 1 1
R 2 2 1 2
C 2 2
R 3 1 2
Q 1
C 3 2
C 1 5
Q 1
Q 2
Q 3
2
1
3
2
| Movie | 1 | 2 | 3 | | :-: | :-: | :-: | :-: | :-: | :-: | | | 0 | - | - | | | 0 | 0 | - | | | 0 | 1 | - | | | 0 | 1 | 1 | | Q 1 => 2 | //Movie 2 wa|s released be|fore Movie 3 | | | 0 | 1 | 1.5 | | | 2.5 | 1 | 1.5 | | Q 1 => 1 | | Q 2 => 3 | | Q 3 => 2 |
对于 30% 的数据，n ≤ 100
对于 100% 的数据，n ≤ 10000