162. 黑盒子

黑盒子代表一个原始的数据库。

它可以用来储存整数数组,并且它拥有一个特殊变量 $i$。

在最开始,黑盒子是空的,并且 $i=0$。

现在对黑盒子进行一系列的操作处理,操作包括以下两种:

  1. ADD(x):表示将 $x$ 加入到黑盒子中。
  2. GET:使 $i$ 增加 $1$,输出黑盒子中第 $i$ 小的数值(即将所有数按升序排序后的第 $i$ 个数)。

下面给出一个具体例子:

序号 操作        i     盒子内数(升序排列后)             输出的值 
1    ADD(3)      0     3   
2    GET         1     3                                    3 
3    ADD(1)      1     1, 3   
4    GET         2     1, 3                                 3 
5    ADD(-4)     2     -4, 1, 3   
6    ADD(2)      2     -4, 1, 2, 3   
7    ADD(8)      2     -4, 1, 2, 3, 8   
8    ADD(-1000)  2     -1000, -4, 1, 2, 3, 8   
9    GET         3     -1000, -4, 1, 2, 3, 8                1 
10   GET         4     -1000, -4, 1, 2, 3, 8                2 
11   ADD(2)      4     -1000, -4, 1, 2, 2, 3, 8   

为了方便描述,下面我们定义两个序列:

  1. $A(1),A(2),…,A(M)$:这个序列由加入到黑盒子内的所有元素按加入顺序排列后得到,上例中的 $A$ 序列为 $(3,1,-4,2,8,-1000,2)$。
  2. $u(1),u(2),…,u(N)$:这个序列的第 $i$ 项表示的是第 $i$ 次 GET 操作时,盒子内元素的数量。上例中的 $u$ 序列为 $(1,2,6,6)$。

现在请你根据给出的序列 $A$ 和 $u$ 求出操作过程中输出的所有数值。

输入格式

输入包括三行。

第一行包含两个整数 $M$ 和 $N$,表示 $A$ 序列和 $u$ 序列的长度。

第二行包含 $M$ 个整数,表示 $A$ 序列的每一个元素。

第三行包含 $N$ 个整数,表示 $u$ 序列的每一个元素。

同行每个数之间用空格隔开。

输出格式

输出操作过程中所有 GET 操作输出的数值。

每个数值占一行。

数据范围

$|A(i)| \le 2 \times 10^9$,
$1 \le N \le M \le 30000$,
对于所有 $p$($1 \le p \le N$), $p \le u(p) \le M$ 成立。

输入样例:

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

输出样例:

3
3
1
2