28446번 - 볼링공 찾아주기

문제

동현이는 볼링을 사랑하는 훌륭한 프로그래머다. 오늘도 볼링을 치고 싶은 동현이는 자신의 볼링공 컬렉션을 보면서 어떤 볼링공을 가져갈지 고민에 빠졌다. 동현이는 매일의 컨디션에 따라 아주 미세한 무게까지 컨트롤하고 싶기 때문에 다양한 무게의 볼링공이 매우 많다. 볼링공을 관리하는 사물함에는 사물함 안에 들어 있는 볼링공들의 무게가 적혀 있고, 하나의 사물함에 여러 개의 볼링공이 들어갈 수 있다. 동현이는 오로지 볼링에만 집중하고 싶기 때문에 볼링공 관리는 여러분에게 맡기기로 했다.

동현이의 요청에 따라 볼링공을 관리해 보자!

요청은 다음과 같다.

• 1 x w: $x$번 사물함에 $w$ 무게의 볼링공을 넣는다.
• 2 w: $w$ 무게를 가진 볼링공이 들어 있는 사물함의 번호를 출력한다.

동현이의 볼링공은 무게가 모두 다르기 때문에 2번 요청의 답은 항상 하나만 존재한다.

2번 요청이 들어올 때, $w$ 무게를 가진 볼링공은 무조건 어딘가에 존재한다.

입력

첫 번째 줄에 요청의 개수 $M(1 \leq M \leq 500,000円)$이 주어진다.

두 번째 줄부터 이어지는 $M$개의 줄에 요청이 주어진다.

• 1 x w: $x$번 사물함에 $w$ 무게의 볼링공을 넣는다. (1ドル \leq x \leq 1,000円,000円,ドル $x$는 정수), (1ドル \leq w \leq 10^9,ドル $w$는 정수)
• 2 w: $w$ 무게를 가진 볼링공이 들어 있는 사물함의 번호를 출력한다. (1ドル \leq w \leq 10^9,ドル $w$는 정수)

2번 요청이 들어올 때, $w$ 무게를 가진 볼링공은 무조건 어딘가에 존재한다.

2번 요청은 최소 1번 이상 들어온다.

출력

2번 요청이 들어올 때 사물함의 번호를 출력한다.

제한

힌트