鸽子的序列

鸽子 hezlik 正在研究可爱的序列问题。

某日，hezlik 决定学习可持久化线段树，并看到了这样一道模板题：

给定一个序列，要求支持单点修改某个值和区间查询第 $k$ 小。

由于 hezlik 并不会可持久化线段树，于是 hezlik 码了整整两天两夜后，最终还是被卡常 TLE 了一个点。

于是 hezlik 愤怒地把这道题丢给了你，并且为了让 hezlik 更加开心，你决定把单点修改换成了区间修改。

输入第一行包括两个正整数 $n,m$，分别表示序列的长度和操作的次数。

接下来一行包括 $n$ 个正整数 $a_1,a_2,\cdots a_n$，表示初始序列。

接下来 $m$ 行，每行包括四个正整数 $o,l,r,k$。若 $o=1$ 表示把区间 $[l,r]$ 中所有数改成 $k$，$o=2$ 表示查询区间 $[l,r]$ 中第 $k$ 小的数，其中数值相同的数算多个。


#### 评测数据规模

对于所有测评数据，$1\leq n,m\leq 10^5$，$1\leq a_i\leq 10^9$，$o\in \{1,2\}$，$1\leq l\leq r\leq n$，$1\leq k\leq 10^9$。

对于每一个 $opt=2$ 的操作，输出一个正整数表示答案，若没有第 $k$ 小输出 $\texttt {INF}$。

3 4
2 3 3
2 1 3 2
2 1 2 4
1 1 2 2
2 1 2 3
10 7
211802054 992321997 219905922 156226463 996357599 68210873 93324663 281334957 173213624 81701293
2 5 5 4
2 7 8 4
1 8 9 3
2 2 4 2
1 9 10 5
1 10 10 1
2 1 6 5

3
INF
INF
INF
INF
219905922
992321997

2024杭电ACM-个人PK赛（2）