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

样例二

样例三

限制与约定

对于$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}$

下载

样例数据下载