黑盒子动态查询问题

题目描述

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

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

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

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

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

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

• $A(1), A(2), \dots, A(M)$：这个序列由加入到黑盒子内的所有元素按加入顺序排列后得到。
• $u(1), u(2), \dots, u(N)$：这个序列的第 $i$ 项表示的是第 $i$ 次 GET 操作时，盒子内元素的数量。

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

输入格式

输入包括三行。

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

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

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

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

输出格式

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

每个数值占一行。

输入输出样例 #1

输入样例

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

输出样例

3
3
1
2

限制条件

• $|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$ 成立。

时间限制

1秒

空间限制

64MB

样例解释

给定：

• $M = 7$，$N = 4$
• $A$ 序列：$(3, 1, -4, 2, 8, -1000, 2)$
• $u$ 序列：$(1, 2, 6, 6)$

$u$ 序列表示：

1. 第 1 次 GET 操作时，盒子内有 1 个元素
2. 第 2 次 GET 操作时，盒子内有 2 个元素
3. 第 3 次 GET 操作时，盒子内有 6 个元素
4. 第 4 次 GET 操作时，盒子内有 6 个元素

操作过程模拟：

1. ADD(3)：盒子 = [3]

   • $u(1) = 1$，所以执行第 1 次 GET
   • $i$ 从 0 变为 1，输出第 1 小的数：3

2. ADD(1)：盒子 = [1, 3]（排序后）

   • $u(2) = 2$，所以执行第 2 次 GET
   • $i$ 从 1 变为 2，输出第 2 小的数：3

3. ADD(-4)：盒子 = [-4, 1, 3]

4. ADD(2)：盒子 = [-4, 1, 2, 3]

5. ADD(8)：盒子 = [-4, 1, 2, 3, 8]

6. ADD(-1000)：盒子 = [-1000, -4, 1, 2, 3, 8]

   • $u(3) = 6$，所以执行第 3 次 GET
   • $i$ 从 2 变为 3，输出第 3 小的数：1

7. ADD(2)：盒子 = [-1000, -4, 1, 2, 2, 3, 8]

   • $u(4) = 6$，但此时盒子有 7 个元素，根据定义 $u(4)$ 表示第 4 次 GET 时盒子内应有 6 个元素
   • 这意味着在第 4 次 GET 时，ADD(2) 还没有发生
   • 所以实际上应该是：在第 6 个 ADD 之后（盒子有 6 个元素时），执行第 3 次和第 4 次 GET
   • 第 4 次 GET：$i$ 从 3 变为 4，输出第 4 小的数：2

因此输出为：

3
3
1
2