未曾设想的道路
时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 800 M，其他语言1600 M
64bit IO Format: %lld

题目描述

小 的家外面有一座山，小 会将这座山分成  段,对于每一段高度相当于是相同的，常年以来，这些山的高度会因为自然因素和人为因素的影响产生改变，小 对这些山很感兴趣，希望知道历史以来一段山中出现过的第  高的山的高度。

输入描述:

第一行两个整数 ，小  将家门口的山分成  段，有  个操作。
第二行有  个整数，表示最开始时山的高度。
接下来  行，每行若干整数，第一个数为操作的编号 。
： 到  这些段的山因为一些自然因素和人为因素的影响，高度都增加了 （ 不一定是大于 ）。
：小  想知道在  到  这些段的山中出现过的所有高度所构成的中第  大的高度。

输出描述:

对于每个操作 1 输出一个答案，每个答案输出占一行，如果不存在第  大的高度则输出历史以来的最小值。
示例1

输入

复制 
8 8
87 -90 95 38 71 -98 -90 -56
1 1 7 1
0 5 8 31
0 1 5 61
0 3 7 5
0 2 3 -46
1 3 5 3
0 1 5 -25
0 4 6 -30

输出

复制 
95
161

说明

开始时的序列为 （其中  表示一个可重集，即对应位置出现过的数）。
查询  的并集  中的最大值为 。
在接下来的  次修改后序列为 。
查询  的并集  中第  大的值为 。

备注:

对于  的数据 。
对于  的数据 。
对于另外  的数据保证没有  操作。
对于另外  的数据保证  操作时 。
对于另外  的数据保证  操作时 。
对于另外  的数据保证  操作时 。
对于另外  的数据保证  操作时 。
对于  的数据 ，，，。