背景

熊孩子们经常看不住自己的钱,总是掉到地上,你伺机而动……

描述

一开始地上没有钱,而每一时刻会发生下列事件之一:

  • ①在某时刻,某个熊孩子往地上掉了一堆价值为A[i]的钱……
  • ②在某时刻,一堆A[i]的钱被某个熊孩子捡走了……(如果本来没有这堆钱,就当他什么都没有发生好了)
  • ③在某时刻,你想知道地上一共还剩多少钱……
  • ④在某时刻,你想知道地上剩下的钱堆的最小价值……(如果没有,请输出0)
  • ⑤在某时刻,价值大于等于A[i]并且小于等于B[i]的钱全被某个熊孩子捡走了……
  • ⑥在某时刻,价值大于等于A[i]并且小于等于B[i]的钱之中,价值最大的那一堆(如果有)被某个熊孩子捡走了……
  • ⑦在某时刻,你想知道价值大于等于A[i]并且小于等于B[i]的钱中钱堆的最小价值……(没有符合题意的钱堆请输出0)
  • ⑧在某时刻,你想知道价值大于等于A[i]并且小于等于B[i]的钱之中的第M[i]到N[i]贵重的这些钱之中的价值总和……(没有符合题意的钱堆请输出0)

数据保证,对于任一时刻,不存在两堆价值相同的钱。

附加说明:如果对⑧操作有细节疑问,可以看看这个具体解释:将价值大于等于A[i]并且小于等于B[i]的钱暂时取出记作Q,然后对于Q中的每一堆钱,如果其价值在Q中的排名(降序排列)大于等于M[i]并且小于等于N[i],则我们称这堆钱符合题意。所要输出的便是Q中所有符合题意的钱堆的价值总和。当然如果没有符合题意的钱堆则输出0。

输入格式

第一行为一个整数N,代表总的时间。

接下来N行,每行若干个整数,表示每个时刻发生的事件。第i+1行表示第i时刻发生的事件。第一个整数Type[i]在[1,8]以内,表示事件代号,如上所述。

  • 如果Type[i]∈{1,2},接下来会有一个整数A[i];
  • 如果Type[i]∈{3,4},接下来不会有任何数;
  • 如果Type[i]∈{5,6,7},接下来会有两个整数A[i] B[i];
  • 如果Type[i]=8,接下来会有四个整数A[i] B[i] M[i] N[i]。

测试数据中,输入数据均为随机生成的。它的意义是:对于每个i,Type[i]有一半概率为1,而其余的概率均等分给各其他合法的Type;每个A[i] B[i] M[i] N[i]均在合法范围内随机生成。

输出格式

对于每个1,2,5,6事件请输出一行OK,对于其他事件请输出询问的答案。

样例输入1

8
3
4
1 250
2 270
7 0 250
8 250 250 2 3
5 70 170
6 120 700

样例输出1

0
0
OK
OK
250
0
OK
OK

样例输入2

30
1 50
1 60
1 70
3
4
2 40
3
4
2 60
3
4
2 50
3
4
1 30
1 80
5 30 100
3
4
1 40
1 90
1 60
5 50 50
6 40 80
7 40 80
8 40 80 2 3
8 40 80 1 2
1 60
8 40 80 1 2
7 60 90

样例输出2

OK
OK
OK
180
50
OK
180
50
OK
120
50
OK
70
70
OK
OK
OK
0
0
OK
OK
OK
OK
OK
40
0
40
OK
100
60

数据范围与约定

  • 对于100%的数据,1≤A[i],B[i],M[i],N[i]≤1000000000。
测试点序号  Type[i]  N         其他特征
1           ≤3       ≤500000   A[i]≤1000000
2           ≤3       ≤500000   无
3           ≤4       ≤500000   A[i]≤1000000
4           ≤4       ≤500000   无
5           ≤6       ≤100000   无
6           ≤6       ≤500000   A[i]≤1000000
7           ≤6       ≤500000   无
8           ≤8       ≤100000   无
9           ≤8       ≤500000   A[i]≤1000000
10          ≤8       ≤500000   无

样例解释

8              # 共有8个时刻,一开始地上没有钱
3              # 现在没有钱,所以输出0
4              # 还是没有钱,所以输出0
1 250          # 地上掉了250大洋
2 270          # 没有一堆价值为270的钱,什么都不会发生
7 0 250        # 大于等于0小于等于250的钱之中最小的一堆为250
8 250 250 2 3  # 大于等于250小于等于250的钱一共就一堆,不存在第二大或第三大,所以输出0
5 70 170       # 没有大于等于70小于等于170的钱,什么都不会发生
6 120 700      # 250的那堆钱终于消失了

第2个样例太长了写不下……

来源

到处都是

不得不说

难道你没发现最后你一块钱都没捡吗?除非你自己是熊孩子之一……