# Practice on Toph

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

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

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 **K**th 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 10^{18}, 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 <= 10^{5}

1 <= X, L <= R <= 10^{18}

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 |

71% Solution Ratio

sagar1230Earliest,

emrul_muFastest, 0.0s

preciousLightest, 1.6 MB

Shahriar2154Shortest, 605B

Login to submit