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 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.
1 <= N, Q, K <= 105
1 <= X, L <= R <= 1018
For each query of type 2, output an integer in a line as described in the problem statement.
| Input | Output |
|---|---|
10 2 8 10 4 9 1 3 5 9 4 10 1 3 2 1 6 3 | 2 |