Range Minimum With Updates

Statement

You have an array of n integers and must process q operations in order. An operation `1 i v` sets the i-th element to v. An operation `2 l r` asks for the smallest value among positions l to r, inclusive. Positions start at 1.

Input

The first line has n and q. The second line has the n initial values. Each of the next q lines is either `1 i v` or `2 l r`.

Output

For every operation of type 2, print the smallest value on its own line, in order.

Constraints

1 <= n, q <= 200000
|value| <= 10^9
There is at least one operation of type 2.

Example 1

5 5
4 2 7 1 9
2 1 5
1 4 8
2 1 5
2 3 5
2 4 4

1
2
7
8

After setting position 4 to 8 the array is 4 2 7 8 9, so the minimum over everything is 2.