Array Query Processing

You are given an integer array \( A \) of length \( N \) and \( M \) queries. Each query is of one of two types:

• Type 1: Given four integers \( 1 \), \( l \), \( r \), \( x \), update the array segment \( A[l..r] \) (1-indexed) by setting every element in this segment to \( x \).
• Type 2: Given four integers \( 2 \), \( l \), \( r \), \( k \), find the \( k \)-th smallest element in the subarray \( A[l..r] \) (1-indexed). It is guaranteed that \( 1 \leq k \leq (r-l+1) \).

After processing all the queries sequentially, output the result of every Type 2 query in the order they appear. If there is no Type 2 query, output nothing.

The \( k \)-th smallest element in a list is defined as the element that would appear in the \( k \)-th position if the list were sorted in non-decreasing order.

inputFormat

The first line contains two integers \( N \) and \( M \) representing the number of elements in the array and the number of queries, respectively.

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

The following \( M \) lines contain four integers each. Each line describes a query in one of the following formats:

• For Type 1 queries: 1 l r x
• For Type 2 queries: 2 l r k

All indices are 1-indexed.

outputFormat

For each Type 2 query, output a single line containing the \( k \)-th smallest element from the specified subarray.

If there are no Type 2 queries, no output should be produced.

## sample

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

5
8

</p>