Sequence Updates and (k)th Smallest Query

You are given a sequence \(a\) of length \(n\) and \(m\) operations.

• Operation 1: For the interval \([l, r]\), change every element equal to \(x\) to \(y\). Specifically, for every index \(i\) such that \(l \le i \le r\) and \(a_i = x\), assign \(a_i = y\).
• Operation 2: For the interval \([l, r]\), output the \(k\)th smallest element. That is, if you sort the subarray \(a_l, a_{l+1}, \dots, a_r\) in non-decreasing order, report its \(k\)th element.

You need to process the operations in the given order.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \le n, m \le 10^5)\), representing 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.

Then \(m\) lines follow. Each line represents an operation:

• If the operation is of the first type, the line contains five integers: 1 l r x y, which means that for every index \(i\) with \(l \le i \le r\), if \(a_i = x\) then set \(a_i = y\).
• If the operation is of the second type, the line contains four integers: 2 l r k, which asks for the \(k\)th smallest element in the subarray \(a_l, a_{l+1}, \dots, a_r\).

outputFormat

For each operation of the second type, output the corresponding answer on a separate line.

sample

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

1
3
3