Dreamrise

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 $n$ teams, each team is given a unique id from 1 to $n$. 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.

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

$\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\ y$: Teams with id $x$ and $y$ played a match. The team with id $x$ is the winner.

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

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

Input

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

$1 ≤ 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

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

Large data set. Use faster I/O.

The win rate is not necessarily an integer.