时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定一个长度为 \(n\) 的整数数组 \(A[1]、A[2]、…、A[N](0≤A[i]≤100)\)，和 \(m\) 个操作：

　　1、\(M\ i\ j\ t\) 把 \(A[i]..A[j]\) 的值都增加 \(t（0≤t≤100）\);

　　2、\(Q\ i\ j\ k\) 查询连续子序列 \(A[i]..A[j]\) 中第 \(k\) 小元素（\(A[i]..A[j]\) 由小到大排序后的第 \(k\) 个元素）。

【输入格式】

　　第一行包含两个整数 \(n\) 和 \(m\)，表示数组有 \(n\) 个元素，\(m\) 表示有 \(m\)个查询操作；
　　接下来的一行包含 \(n\) 个整数，第 \(i\) 个整数表示 \(A[i]\)；
　　再接下来的 \(m\) 行，每行表示一个操作.

【输出格式】

　　对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

【输入输出样例】

　Input

5 3
3 2 1 4 7
Q 1 4 3
M 3 5 1
Q 2 5 3 

　Output

3
5

【数据说明】

　　对于 \(20\%\) 的数据 \(1≤n,m≤100\)。
　　对于 \(40\%\) 的数据 \(1≤n,m≤1000\)。
　　对于 \(100\%\) 的数据 \(1≤n,m≤10000\)，任何时候序列中的元素值不超过 1000000。

【来源】

　　Mr.he