[永不止步-2017]_区间第K大

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

2017年山东理工大学SDUTACM集训队在“第二届中国高校计算机竞赛团体程序设计天梯赛”中以珠峰争鼎组(原985、211高校)全国总决赛第7名的成绩获得高校一等奖。

 

众所周知,区间第k大数是一个经典问题,LDQ最近在思考这个问题的新解法。

可是由于他最近忙着比赛,因此请你帮助他解决这个问题。问题描述如下:

给出 n 个数 ai,q 次操作 。
操作有两种:
1. 给出 l, r, v 区间 [l, r] 的数的值增加 v
2. 给出 l, r, k 输出区间 [l, r] 中第 k 大的数, 保证 k >= r - l + 1 。

Input

多组输入,组数不超过200。
对于每一组第一行输入 n 和 q 。
接下来一行输入 n 个正整数 ai。
接下来 q 行,每行输入四个整数,第一个值为 1 表示第一种操作,为 2 表示第二种操作,接下来三个数为 l, r, v | k 。

( 1 <= n <= 1e5, 1 <= l, r <= n, 1 <= v <= 1e4, 1 <= k <= 5,1 <= ai <= 1e4,1 <= q <=1e5 )

Output

对于每个操作2 ,输出一个整数,即为区间 [l, r] 中第 k 大的数 。

Sample Input

5 5
7933 3729 2547 9919 8005
1 3 5 425
2 3 4 1
1 2 4 7745
2 2 5 2
2 5 5 1

Sample Output

10344
11474
8430

Hint

Source

【重聚--SDUTACM十周年庆典专场赛】Fish