Description

Xiao Z invented a new movie rating system with three kinds of operations: releasing a new movie, rating a movie, and querying a movie’s rank.

• When releasing a new movie: if none of its leading actors have appeared before, the new movie’s rating is $0$. Otherwise, its initial rating equals the rating of the most recent previously released movie that shares at least one leading actor with it.
• When rating a movie: its rating becomes the average of its previous rating and the new score.
• When querying a rank: output the ID of the movie whose current rank is $x$. The highest rating ranks first. If multiple movies have the same rating, the one released earlier ranks higher. All ratings are between $0$ and $5$.

Input Format

The first line contains $n$, the number of operations. Then $n$ lines follow, each being one of the following:

1. Q x: query the movie ID currently ranked $x$.
2. R ID x actor1 actor2 ... actorx: release a new movie with ID $ID$, which has $x$ leading actors $actor1, actor2, \dots, actorx$.
3. C ID score: rate movie $ID$ with the score $score$; the movie’s new rating becomes the average of its previous rating and $score$.

Additional rules:

• All movie IDs are distinct.
• Each movie has at most $5$ leading actors.

Constraints:

• $1 \leq actor_i \leq 10^5$.
• $1 \leq ID \leq 10^5$.
• For $30\%$ of the testdata, $n \leq 100$.
• For $100\%$ of the testdata, $n \leq 10000$.

Output Format

For each query operation, output the corresponding movie 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

Hint

• The initial rating of a new movie is $0$ if none of its leading actors have appeared before; otherwise, it equals the rating of the most recently released earlier movie that shares at least one leading actor.
• After a rating operation C ID score, the new rating becomes the average of the current rating and $score$.
• If multiple movies have the same rating, the earlier released one ranks higher. For example, if Movie $2$ and Movie $3$ have the same rating, then a query Q $1$ returns $2$ because Movie $2$ was released earlier.

Translated by ChatGPT 5