Migrated from Lutece 2753 特雷森学院的训练员

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在特雷森学院，训练员需要根据马娘的状态来安排训练。马娘们的心情也是一个重要的影响要素，为了选择合适的训练方式，训练员需要了解序号在一个区间上的马娘们的心情状况。请你帮忙写一个程序来帮忙解决这个问题。

现在有 $N$ 只马娘，序号从 $1$ 到 $N$，心情值可以用一个 $[0,10^8]$ 的整数来表示，马娘们的心情有时候也会发生变化。训练员需要了解的状况以及马娘的心情变换可以概括成下面三种描述：

1、训练员想知道对于序号在 $[l,r]$ 上心情值低于 $k$ 的的马娘有多少
2、训练员想知道对于序号在 $[l,r]$ 上心情值第 $k$ 小（心情从小到大排名为 $k$）的的马娘心情值是多少
3、序号 $pos$ 的马娘心情值变为 $k$

Input

第一行两个整数 $N,M$，表示马娘的数量和接下来的描述次数
第二行 $N$个整数表示初始时马娘们的心情值
接下来 $M$行，每行第一个整数 $opt$ 表示描述的种类

$opt=1$，之后有三个数 $l,r,k$，表示询问序号在 $[l,r]$ 上心情值低于 $k$ 的的马娘有多少
$opt=2$，之后有三个数 $l,r,k$，表示询问序号在 $[l,r]$ 上情值第 $k$ 小的的马娘心情值是多少 $opt=3$，之后有三个数 $pos,k$，表示序号 $pos$ 的马娘心情值变为 $k$

Output

对于描述$1$和$2$，输出一个整数表示答案

Samples

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
1 3 9 5
2 2 8 5

2
4
2
5
4

Constraints

$1 \le N,M \le 5\times 10^4 , 1 \le l \le r \le N , 1 \le pos \le n$ 保证心情值在 $[0,10^8]$，描述二的 $k$ 保证一定有解

Resources

2022 UESTC ICPC Training for Data Structures