# Complex Operations

Limits 1s, 512 MB

You are given an array A of length N.
You have to perform two different types of operations.

In the first type of operation, you will be given an integer X and you will need to subtract it from all numbers in the given array A.

For example, an operation denoted as 1 7 represents that you have to subtract 7 from all the numbers in array A. Here, the leading 1 represents that this operation is of first type.

In the second type of operation, you will be given 3 integers L, R, and K, and you need to print the Kth smallest number among the numbers of the array whose values are between L and R (both inclusive). If there is not enough numbers in between L and R, then print -1.

For example, an operation denoted as 2 1 7 4 represents that at first, you have to find all the numbers in array A whose values are within [1, 7] range and then you have to print the 4th number among these numbers. Here, the leading 2 represents that this operation is of second type.

Your task is to perform Q operations in the given array A.

## Input

Input starts with two integers N and Q followed by a line of N space-separated non-negative integers, having value not greater than 1018, representing array A. The following Q lines contain space-separated integer numbers and begin with either 1 or 2 representing the type of query and then followed by other space-separated integers depending upon type of query as described in the problem statement.

#### Constraint:

1 <= N, Q, K <= 105

1 <= X, L <= R <= 1018

## Output

For each query of type 2, output an integer in a line as described in the problem statement.

## Sample

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

2


Login to submit.

### Statistics

71% Solution Ratio
sagar1230Earliest, Nov '19
Paul72Fastest, 0.0s
preciousLightest, 1.6 MB
saif.71Shortest, 567B
Toph uses cookies. By continuing you agree to our Cookie Policy.