K-th Smallest Query with Range Updates

You are given a sequence of length \(n\) consisting of integers. The sequence is 1-indexed. You need to support \(m\) operations on this sequence. There are two types of operations:

• Query operation: Given three integers \(l\), \(r\), and \(k\), output the \(k\)-th smallest value in the subarray \([l, r]\). It is guaranteed that \(1 \leq k \leq r-l+1\).
• Update operation: Given three integers \(l\), \(r\), and \(k\), add \(k\) to each element in the subarray \([l, r]\).

Formally, you are given an array \(a_1,a_2,\dots,a_n\). For an operation of type 1, you must answer the query: "what is the \(k\)-th smallest element of \(\{a_l,a_{l+1},\dots,a_r\}\)?". For an operation of type 2, update every \(a_i\) for \(l \leq i \leq r\) by setting \(a_i = a_i + k\).

Please note that the operations are given in an online manner and the updates persist across queries.

inputFormat

The first line contains two integers \(n\) and \(m\): the length of the sequence and the number of operations.

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) representing the initial sequence.

Each of the following \(m\) lines describes an operation in one of the following formats:

• \(1\ l\ r\ k\): Query the \(k\)-th smallest number in the subarray \([l, r]\).
• \(2\ l\ r\ k\): Add \(k\) to every element in the subarray \([l, r]\).

outputFormat

For each query operation (type 1), output the \(k\)-th smallest number in the specified range on a new line.

sample

5 5
5 1 3 2 4
1 1 5 3
2 1 3 2
1 1 3 2
2 4 5 -1
1 2 5 3

3
5
3