U71972 鸽子的序列

鸽子 hezlik 正在研究可爱的序列问题。 某日，hezlik 决定学习可持久化线段树，并看到了这样一道模板题： 给定一个序列，要求支持单点修改某个值和区间查询第 $k$ 小。 由于 hezlik 并不会可持久化线段树，于是 hezlik 码了整整两天两夜后，最终还是被卡常 TLE 了一个点。 于是 hezlik 愤怒地把这道题丢给了你，并且为了让 hezlik 更加开心，你决定把单点修改换成了区间修改。

输入第一行包括两个正整数 $n$ 和 $m$，分别表示序列的长度和操作的次数。 接下来一行包括 $n$ 个正整数 $a_i$，表示初始序列。 接下来 $m$ 行，每行包括四个正整数 $opt\,l\,r\,k$。若 $opt=1$ 表示把区间 $[l,r]$ 中所有数改成 $k$，$opt=2$ 表示查询区间 $[l,r]$ 中第 $k$ 小的数，其中数值相同的数算多个。

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

 **注：本题可能有一定程度上的卡常，尽量让代码常数小一些。** [solution](https://blog.csdn.net/hzk_cpp/article/details/90446442).