Xiao Z has invented a new movie rating system. This system has three operations: releasing a new movie, rating a movie, and querying the ranking of movie ratings. The system works as follows: if a new movie is released, and none of its actors have appeared in any previous movies, the rating of this new movie is 0. Otherwise, the rating of this new movie is the average of the ratings of the most recent movie that shares at least one actor with it. If a movie is rated, its rating becomes the new rating. If a query for a ranking is made, the corresponding movie ID is returned based on the ranking. The movie with the highest rating is ranked first. If multiple movies have the same rating, the one released earliest is ranked higher. Movie ratings are between 0 and 5.

Input

The first line of input contains $n$, the number of operations. The next $n$ lines each contain one of the following three operations:

1. Q x: Query the ID of the movie currently ranked $x$.
2. R ID x actor1 actor2 ··· actorx: Release a new movie with ID ID, which has $x$ actors: actor1, actor2, ..., actorx.
3. C ID score: Rate the movie with ID ID with a score of score.

It is guaranteed that all movie IDs are distinct, and each movie has at most 5 actors. $1 \le actor_1, actor_2, \dots \le 10^5$ $1 \le ID \le 10^5$

Output

For each query operation, output the ID of the movie with the corresponding ranking.

Examples

Input 1

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

Output 1

2
1
3
2

Note

The ratings of movies 1, 2, and 3 over time:

Q 1 => 2 // Movie 2 was released before Movie 3 Q 1 => 1 Q 2 => 3 Q 3 => 2

Constraints

For 30% of the data, $n \le 100$.

For 100% of the data, $n \le 10000$.