題目描述

您需要寫一個數據結構，支持區間覆蓋與求區間 K 小值。

輸入格式

第一行兩個整數，分別為 $n,q$，分別表示序列長度與詢問次數。

第二行 $n$ 個整數，第 $i$ 個數為 $a_i$，表示第 $i$ 個位置的初始元素。

接下來 $q$ 行，每行一個字符，三個整數。

• 格式為 Q l r k，表示查詢 $[l,r]$ 區間第 $k$ 小元素的值。
• 格式為 C l r c，表示將 $[l,r]$ 區間的數都改為 $c$。

輸出格式

對應每次詢問。

樣例輸入輸出

5 5
1 2 3 4 5
Q 1 4 3
Q 2 5 3
C 1 1 4
Q 1 4 3
Q 1 3 2

3
4
4
3

5 8
1 5 4 2 3
C 1 3 4
Q 2 3 2
C 2 4 1
Q 1 5 4
C 1 5 5
C 3 4 2
C 4 5 3
Q 1 5 4

4
3
5

說明/提示

對於 $100\%$ 的數據，$1\leq n\leq10^5$，$1\leq q\leq2\times10^5$，$1\leq c\leq n$。

數據很水，但是不保證一些奇奇怪怪的暴力可以拿到高分。