Domagoj's favorite school subject is P.E. Every P.E. class starts with warm-up exercises. The teacher has an interesting way of choosing the student who will lead the warm-up. The students stand in a line sorted by their height. The teacher will choose the student that is standing in the middle of the line. If two students are in the middle, he will choose the shorter one. For example: if the students have heights , the student with height will lead the warm-up exercises.

Domagoj does not remember how tall his classmates are. Luckily, next to him
stands Lovro, who is very good at estimating people's heights. He gives Domagoj statements: "*There are
students entering the gym with height *". After every statement said by Lovro, Domagoj is interested
in the height of the student who will lead the warm-up, if only the students who entered the gym come to
P.E. class. Help him answer his questions!

#### Input Specification

The first line contains the integer , the number of Lovro's statements.

The following lines contain two integers , the height and the number of students in Lovro's statement.

#### Output Specification

In the of lines, output the answer to Domagoj's question after of Lovro's statements.

#### Constraints

Subtask | Points | Constraints |
---|---|---|

1 | 19 | |

2 | 26 | |

3 | 29 | |

4 | 36 | No additional constraints. |

#### Sample Input 1

```
3
2 1
3 1
1 1
```

#### Sample Output 1

```
2
2
2
```

#### Sample Input 2

```
4
17 2
23 5
11 4
9 5
```

#### Sample Output 2

```
17
23
17
11
```

#### Sample Input 3

```
3
10 20
100 5
1000 5
```

#### Sample Output 3

```
10
10
10
```

## Comments