UVA1480 Jewel

Jimmy 想为他的女朋友做一条特别的项链，他买了很多大小不同的珠子（没有大小相同的珠子）。因为项链太长了， Jimmy 记不住所有的珠子。所以，他向你寻求帮助。 一开始，项链上没有珠子，也就是一条空项链。 Jimmy 总是从项链的右侧加入新的珠子，使项链越来越长。我们规定，左边的第一颗珠子位置为 $1$ ，左边的的第二颗珠子位置为 $2$ ，以此类推。 Jimmy 会询问珠子的位置，第几大（当前将项链上的所有珠子从小到大排序后的位置）和大小。也就是说你需支持以下四个操作。 1、 Insert $x$: 将大小为 $x$ 的珠子从右侧加入项链( $0 < x < 2^{31} $ ,并且 $x$ 不等于当前项链中任何珠子的大小）。 2、 Query 1 $s$ $t$ $k$: 询问 $s$ 到 $t$ 之间（包括 $s$ 和 $t$ ）第 k 小的珠子, $ 1 \le s \le t \le L $ ( L 为当前项链的长度），并且 $ 1 \le k \le \min(100,t-s+1)$ 。 3、 Query 2 $x$ : 询问当前将项链上的所有珠子从小到大排序后, $x$ 大小的珠子的位置，答案在 $ 1 $ 和 $ L $ 之间。 4、 Query 3 $ k $ :询问当前项链中第 $ k $ 小的珠子的大小( $ 1 \le k \le L $ )。

第一行是一个整数 $ N $ ，表示操作次数。接着是 $ N $ 行，每行包含一个操作，如上所述。“ Insert ”操作的数量不超过 $ 100000 $ ，并且“ Query_1 ”“ Query_2 ”和“ Query_3 ”都小于 $ 35000 $ 。

输出4行。第一行是“ Case $ T $ :”，其中 $ T $ 是数据的编号。接下来的 $ 3 $ 行分别表示“ Query_1 ”、“ Query_2 ”和“ Query_3 ”的结果之和。 样例说明：$ 5 $ 个询问的答案分别为 $ 6 $ 、 $ 4 $ 、 $ 3 $ 、 $ 4 $ 、 $ 1 $ 。