#550. 黑盒子

黑盒子

题目描述

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

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

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

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

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

下面给出一个具体例子:

_G5WO5S_TH3~_JGD`_OYB5W.png

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

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序列的每一个元素(数据保证 uiui+1u_{i} ≤ u_{i+1} )。

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

输出格式

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

每个数值占一行。

样例

输入样例:

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

输出样例:

3
3
1
2

数据范围与提示

A(i)<=2109,|A(i)|<=2∗10^{9}, 1NM30000,1≤N≤M≤30000, 对于所有 p1pNp(1≤p≤N , pu(p)Mp≤u(p)≤M 成立