Array Query Processing

You are given an array of N integers and Q queries. The queries are of two types:

• Type 1: "1 l r" – Reverse the subarray from index \(l\) to \(r\) (1-indexed). In other words, if the current array is \(A = [a_1, a_2, \ldots, a_N]\), then after this operation, the segment \(a_l, a_{l+1}, \ldots, a_r\) becomes \(a_r, a_{r-1}, \ldots, a_l\).
• Type 2: "2 l r k" – Find and output the \(k\)-th smallest element in the subarray from index \(l\) to \(r\) (1-indexed). Here, \(1 \le k \le (r-l+1)\) and the element order is determined after sorting the subarray in non-decreasing order.

The operations are applied sequentially. Note that reversing a subarray may affect the outcome of subsequent queries.

Input Constraints:

• \(1 \le N \le 10^5\)
• \(0 \le Q \le 10^5\)
• All array elements and query parameters are integers.

Examples:

Input:
6 4
5 3 8 6 2 7
1 2 5
2 1 6 3
2 2 4 1
1 3 6
Output:
5
2
Input:
5 1
1 2 3 4 5
2 1 5 3
Output:
3

</p>

inputFormat

The first line contains two space-separated integers \(N\) and \(Q\), representing the length of the array and the number of queries, respectively.

The second line contains \(N\) space-separated integers representing the array \(A\).

Each of the following \(Q\) lines contains a query in one of the two formats:

• For a reverse operation: 1 l r
• For a k-th smallest query: 2 l r k

outputFormat

For each query of type 2, output the \(k\)-th smallest element in the specified subarray on a new line.

## sample

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

5
2

</p>