Wowow

월드 오브 워크래프트의 세계에는 경쟁이 매우 치열한 랭킹 래더가 있습니다. 플레이어들은 시간이 지나면서 자신의 레이팅을 바꾸고, 점점 더 많은 친구를 포함한 새로운 플레이어들이 끊임없이 게임에 합류합니다.

당신과 친구들은 모두의 점수를 담은 간단한 데이터베이스를 관리하고 싶어 합니다. 그룹의 컴퓨터 과학자인 당신이 이 데이터베이스를 관리하는 임무를 맡았습니다. 친구들을 실망시키지 마세요!

첫째 줄에 연산의 개수를 나타내는 정수 $N$ ($1 \le N \le 1{,}000{,}000$)이 주어집니다. 이어지는 $N$개의 줄에는 다음 세 가지 명령 중 하나가 주어집니다.

• N X R — 새로운 친구가 추가됩니다. $X$ ($1 \le X \le 1{,}000{,}000$)는 새 친구의 식별자이고, $R$ ($1 \le R \le 10^8$)은 그 친구의 레이팅입니다.
• M X R — 이미 존재하는 친구의 레이팅을 수정합니다. $X$는 데이터베이스에 이미 있는 친구의 식별자이고, $R$은 그 친구의 새로운 레이팅입니다.
• Q K — 질의입니다. $K$는 $1 \le K \le 1{,}000{,}000$을 만족하는 정수이며, 그 시점에 데이터베이스에 있는 친구 수를 넘지 않습니다.

입력에 등장하는 모든 레이팅 값은 서로 다릅니다.

각 Q K 명령마다, 그 시점의 데이터베이스에서 $K$번째로 높은 레이팅을 가진 친구의 식별자를 한 줄에 출력합니다. $K = 1$은 가장 높은 레이팅의 친구, $K = 2$는 두 번째로 높은 친구를 의미하며, 이런 식으로 계속됩니다.