Teemu is an intern at the Department of Spatial Planning of the city of Oopse. His task is keep track of the heights of the buildings on Wave street.

Wave street which can be modeled as a straight line with integer building numbers. In his work, Teemu encounters two kinds of requests: update the height of the building a to be b, and find the maximum height of buildings in a continuous stretch between buildings a and b, inclusive.

Input

First line contains one integer q, the number of requests.

Each of the following q lines consists of three integers t, a and b. If t=0, the query means that Teemu needs to update the height of building a to be b. If t=1, Teemu needs to tell the height of the tallest building between buildings a and b, inclusive.

Initially there are no buildings on Wave street, that is the height of all buildings is 0.

Output

For each query of type t=1, print a single line of output, the height of the tallest building.

Constraints

• 1 \le q \le 10^4
• If t=0, 1 \le a \le 10^{18}, 0 \le b \le 10^{18}
• If t=1, 1 \le a,b \le 10^{18}

Example

Input:

10
0 100 1000
0 200 1001
1 100 200
1 101 199
0 200 200 
1 150 250
0 300 250
1 150 450
0 100 0
1 0 200

Output:

1001
0
200
250
200