Marisa plays poker - MarisaOJ: Marisa Online Judge

Given an array

A

$A$ of

n

$n$ integers, there are

q

$q$ queries, each falling into one of two types: -

1 l r k

$1 l r k$ : Find the

k

$k$ -th smallest number in the subarray

A_{l . . . r}

$A_{l...r}$ . -

2 l r x

$2 l r x$ : For every

l \leq i \leq r

$l \le i \le r$ , increment

A_{i}

$A_i$ by

x

$x$ . Find the answers for each query of type

1

$1$ . ### Input - The first line contains two integers

n, q

$n, q$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

q

$q$ lines each contain a query in the specified format. ### Output - Print an integer as the answer for each query of type

1

$1$ . ### Constraints -

1 \leq n, q \leq 10^{5}

$1 \le n, q \le 10^5$ . -

0 \leq | A_{i} |, | x | \leq 2 \times 10^{4}

$0 \le |A_i|, |x| \le 2 \times 10^4$ . -

1 \leq k \leq r - l + 1

$1 \le k \le r - l + 1$ . ### Example Input:

1111111

$1 1 1 1 1 1 1$

Output:

1

$1$

Square root decomposition
	Frequency
	Tree query
	Inversions query
	Nearest vertex
	Dominating color
	String occurences 3
	Inversions query 2
	Pair
	Sparse update
	Tree
	Range query
	String concatenation
	Subarray distance
	Chameleon
	Knapsack
	Bit counting
	Subsequence queries
	Sub-subsequence
	Delete numbers
	Mode
	Marisa is happy
	Inversions query 3
	Upperbound
	23 path
	Yet another square root decomposition problem
	Marisa plays poker
	Wonderful world

Topic

Data structure

Rating

2400

Source

Ynoi

Solution (1)

Solution