Black Box

Description 我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令： ADD(x)：把元素x放入黑匣子； GET：把i加1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。 下面是一个11个命令的例子： 编号 命令 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 现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多个有30000个。 定义ADD命令的个数为M个，GET命令的个数为N个。 我们用下面得两个整数序列描述命令序列： 1．A(1),A(2),……,A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A=(3,1,-4,2,8,-1000,2)。 2．u(1),u(2),……,u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u=(1,2,6,6)。 你可以假定自然数序列u(1),u(2),……,u(N)以非降序排列，N≤M，且对于每一个p（1≤p≤N）有p≤u(p)≤M 现在要求找出对于给定的命令串的最好的处理方法。ADD 和 GET 命令分别最多有30000个。 现在用两个整数数组来表示命令串： 1. A(1), A(2), ..., A(M): 一串将要被放进Black Box的元素。每个数都是绝对值不超过2 000 000 000 的整数 M <= 30000。例如上面的例子就是A=(3, 1, -4, 2, 8, -1000, 2). 2. u(1), u(2), ..., u(N): 表示第u(j)个元素被放进了Black Box里后就出现一个GET命令。例如上面的例子中u=(1, 2, 6, 6). 输入数据不用判错。 Input 题目有多组输入数据！ 第一行是一个表示输入组数的整数 N ，隔一空行之后是 N 组输入数据，每组输入数据之间都有一行空行隔开，各组数据都是按上面的形式输入。 Output 输出包含 N 组输出数据，每一组之间用一个空行隔开。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=442 [PDF](https://uva.onlinejudge.org/external/5/p501.pdf) 



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

3
3
1
2