Dreamrise

NJRafi Replay of Father Timm Mem...
Limits 2s, 512 MB

You are building a new game called Dreamrise. The game is played by 2 teams and each match usually lasts around 15 minutes. You are currently building the leaderboard feature. There will be multiple leaderboards both worldwide and regional. In a leaderboard with nn teams, each team is given a unique id from 1 to nn. Every team is ranked based on its win rate within a leaderboard. If multiple teams have the same win rate, they are given the same rank. A team is unranked until they play any game.

Win rate=Number of games wonNumber of games played\text{Win rate} = \frac{\text{Number of games won}}{\text{Number of games played}}

The rank of a team=Number of teams having higher win rate+1\text{The rank of a team} = \text{Number of teams having higher win rate} + 1

You have to support 3 types of operations to implement the leaderboard feature.

  • 1 x y1\ x\ y: Teams with id xx and yy played a match. The team with id xx is the winner.

  • 2 x2\ x: Print the current rank of the team with id xx. If the team is unranked, print -1.

  • 3 z3\ z: Print the id of the team having a rank of zz. If no team is ranked zz currently, print -1. If multiple teams have the rank zz, print the team with the smallest ID.

Input

The first line of input contains two integers nn (1n1051 ≤ n ≤ 10^5) and qq (1q51051 ≤ q ≤ 5*10^5), denoting number of teams and number of operations respectively. Next qq lines will have one of the 3 operations described in statement.

1x,y,zn1 ≤ x, y, z ≤ n.

Output

Print the desired answer for the operation of type 2 and 3. Do not print anything for operation of type 1.

Sample

InputOutput
5 10
1 2 1
1 2 3
1 1 5
1 3 5
2 1
2 4
3 2
3 4
3 3
3 5
2
-1
1
5
-1
-1

Team 2 played with Team 1, Team 3 and won both matches. Both team 1 and team 3 won with Team 5. Team 4 hasn't played any match yet.

RankTeam IDWin RateMatch Played
12100%2
2350%2
2150%2
450%2
Unranked4n/a0

Large data set. Use faster I/O.

The win rate is not necessarily an integer.

Submit

Login to submit.

Statistics

22% Solution Ratio
jamil314Earliest, Nov '20
jamil314Fastest, 0.6s
fsshakkhorLightest, 9.2 MB
jamil314Shortest, 2237B
Toph uses cookies. By continuing you agree to our Cookie Policy.