Bowling Ball Finder

Time limit1sMemory limit1024 MB

Summary

Each type 1 request puts a ball of a given weight into a locker, and each type 2 request asks which locker holds the ball of a given weight.

Level: Easy3 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

Donghyun is an excellent programmer who loves bowling. Today he wants to bowl again, and while looking over his collection of bowling balls, he cannot decide which one to take. He wants to control even tiny differences in weight depending on his condition each day, so he owns a very large number of balls with many different weights. The locker that stores the balls lists the weights of the balls inside it, and one locker can hold several balls. Donghyun wants to focus only on bowling, so he asks you to manage the balls.

Manage the bowling balls as Donghyun requests.

The requests are as follows.

1 x w: Put a ball of weight $w$ into locker $x$ .
2 w: Print the number of the locker that holds a ball of weight $w$ .

All of Donghyun's balls have different weights, so the answer to a type 2 request is always exactly one locker.

When a type 2 request comes in, a ball of weight $w$ always exists somewhere.

Input

The first line contains the number of requests $M$ ( $1 \leq M \leq 500\,000$ ). The next $M$ lines contain the requests.

1 x w: Put a ball of weight $w$ into locker $x$ . ( $1 \leq x \leq 1\,000\,000$ , $x$ is an integer), ( $1 \leq w \leq 10^9$ , $w$ is an integer)
2 w: Print the number of the locker that holds a ball of weight $w$ . ( $1 \leq w \leq 10^9$ , $w$ is an integer)

When a type 2 request comes in, a ball of weight $w$ always exists somewhere.

There is at least one type 2 request.

Output

For each type 2 request, print the number of the locker.

Examples2

Example 1

Input

Expected output

7
15

Example 2
Input
```
4
1 900 1
2 1
1 1 10000
2 10000
```
Expected output
```
900
1
```