汪了个汪（wow）

1s,1024MB

题目描述

这是一道构造题， 建议先做 $\text{T3}$。

给定一个长度为 $n$ 的序列 $a$， 支持下列两种操作 $q$ 次。

• $\texttt{1 x}$： 对于 $i\in[1,n]$， 令 $a_i=\lfloor\dfrac{a_i+x}{2} \rfloor$。

• $\texttt{2 l r k}$： 求区间 $[l,r]$ 内第 $k$ 大的数。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个正整数表示初始序列 $a$。

接下来 $q$ 行表示询问。

输出格式

对于每个 $2$ 询问， 输出一行表示答案。

样例1

样例1输入

5 8
3 3 4 3 2
2 3 3 1
1 4
1 3
2 2 4 1
2 2 3 1
2 1 2 2
1 3
2 1 4 2

样例1输出

4
3
3
3
3

数据范围

$1\leq n, q\leq 3\times 10^5,1\leq a_i,x\leq 10^9,1\leq l\leq r\leq n,1\leq k\leq r-l+1$。