Veshy has a box with items, the th of which has a "goodness" of on Veshy's standards. Over a period of minutes, one of two events may occur. On the th minute, either Veshy's standards have changed and the th item's "goodness" has changed to , or he wants to know the goodness of the th best item in the subarray of items, .

**It is recommended that Python users use PyPy instead.**

#### Constraints

In all subtasks,

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 3 [60%]

No additional constraints.

#### Input Specification

The first line contains two space-separated integers, and .

The next line contains integers, the th of which being .

lines follow, each of which are either in the form:

`1 a b`

- the th item now has goodness

`2 l r c`

- Veshy wants to know the goodness th best item in the subarray of items:

#### Output Specification

For each query, output the goodness of the th best item in the subarray of items. It is guaranteed that there are at least items in the subarray.

#### Sample Input

```
5 5
3 15 19 7 14
2 2 4 2
1 2 9
2 1 2 2
1 5 17
2 1 5 3
```

#### Sample Output

```
15
3
9
```

## Comments