Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Complex Operations

By Bishal_G · 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


Discussion
Statistics

71% Solution Ratio

sagar1230Earliest, 1w ago

emrul_muFastest, 0.0s

preciousLightest, 1.6 MB

maruf089Shortest, 636B

Submit

Login to submit