Moorhsum和LambEater是好朋友。
省选共有n所学校参加,每所学校有若干选手;第 $i$ 所学校有一个名额上限 $a_i$ 。
每名选手有一个省选总分,这些分数两两不同。
省队是总分之和最大的人数$ \leq k$ 的选手集合,使得集合中属于第i所学校的选手$ \leq a_i$ 个。
作为Moorhsum的好朋友,在官方名单公布前,LambEater想算出省队集合。但是LambEater太菜了,于是他向你求助。你能帮帮他么?
输入格式
第一行两个正整数 $n$ , $k$ 代表学校数量和省队人数上限
随后 $n$ 个正整数 $a_i$ ,含义见题面
随后一个整数 $q$ ,代表操作次数
每个操作形如 $1$ $x$ $y$ 或 $-1$ $x$ $y$
$1$ $x$ $y$ 表示加入一个$x$校选手,其分数为$y$
$-1$ $x$ $y$ 表示删去一个$x$校选手,其分数为$y$。保证删去前这样的选手存在。
输出格式
每次操作后,如果有新选手进入省队,输出一行两个数表示其学校和分数,中间用空格隔开。
可以证明,每次操作后这样的新选手至多有一个。
样例一
input
5 2 9 10 9 8 6 10 1 1 962610 -1 1 962610 1 1 458121 1 2 709525 -1 1 458121 -1 2 709525 1 3 851381 -1 3 851381 1 4 418899 1 5 110519
output
1 962610 1 458121 2 709525 3 851381 4 418899 5 110519
explanation
第一次操作后1 962610进入省队第二次操作后该选手被移出
第三次操作后1 458121进入省队
第四次操作后2 709525进入省队
第五次操作后1 458121被移出
第六次操作后2 709525被移出
第七次操作后1 851381进入省队
第八次操作后该选手被移出
第九次操作后4 418859进入省队
第十次操作后5 110519进入省队
样例二
见样例数据下载样例三
见样例数据下载限制与约定
对于$30\texttt{%}$的数据 $n$,$q \leq 5000$
另有$20\texttt{%}$的数据 $a[i] = k$
另有$20\texttt{%}$的数据 $a[i] = 1$
对于$100\texttt{%}$的数据 $n, q \leq 500000$,$1 \leq k \leq 10^9$,$1 \leq ai \leq 10^9$,$1 \leq x \leq n$,$0 \leq y \leq 10^9$
数据保证加入选手的 $y$ 两两不同。
时间限制:$3\texttt{s}$
空间限制:$512\texttt{MB}$