Greninja is helping Zygarde cut trees.

There are trees in the forest of Kalos. The height of the -th tree is . Since no two trees are exactly same, is a permutation of . Zygarde wants Greninja to do operations of three following types:

1. Sort in increasing order.
2. Sort in decreasing order.
3. Find the maximum positive integer that exists integers satisfy for .

Without Battle Bond, Greninja cannot do these operations by itself. Can you help him?

输入描述:

The first line contains two integers  (), denoting the number of trees and the number of operations.

The second line contains  integers  (), denoting the initial height of trees. It's guaranteed that  is a permutation of .

For the -th line in the following  lines, there are three integers  (), denoting the type of the -th operation and the range of the -th operation.

输出描述:

For each operation in type 3, print an integer in a single line, denoting the answer of this operation.

3 3
1 3 2
3 1 3
1 2 3
3 1 3

2
3

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

5

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

5
6
10

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

5
5

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

4
1

备注:

In the first example, the initial height of trees is . In the first operation, the maximum  is , since  and  (so  cannot be ). After the second operation, the height of trees becomes . In the third operation, the maximum  is , since  and .