Background

Problem Description

Yuno is not very good at playing poker.

So she came up with a data structure problem.

You are given a sequence $a$ of length $n$. You need to support $m$ operations of two types:

1. Query the $k$-th smallest value in the interval $[l, r]$.
2. Add $k$ to every element in the interval $[l, r]$.

Input Format

One line with two integers $n, m$.

The next line contains $n$ integers; the $i$-th integer represents $a_i$.

The next $m$ lines each contain four integers $opt, l, r, k$, where $opt$ indicates which type of operation it is.

Output Format

For each query, output one number as the answer. If there is no solution, output $-1$.

1 1
1
1 1 1 1

1

Hint

Idea: nzhtl1477.

Solution: nzhtl1477 ($O(m\sqrt{n}(\Delta+\log n))$) solution, ccz181078 ($O(m\sqrt{n\log n})$) solution.

Code: nzhtl1477 ($O(m\sqrt{n}(\Delta+\log n))$) code, ccz181078 ($O(m\sqrt{n\log n})$) code.

Data: nzhtl1477.

Constraints: $1\leq l\leq r \leq n\leq 10^5$, $1 \leq m \leq 10^5$, $-2\times 10^4\leq a_i, k\leq 2\times 10^4$, $opt \in \{1, 2\}$.

$\text{upd 2022.8.18}$: A new set of hack testdata has been added.

Translated by ChatGPT 5