题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2,..., a_n$。 $a$ 的子序列 $\{a_{i_1}, ai2,..., a_{i_l}\}$ 合法，当且仅当其满足对所有 $1 \leq j < l, i_{j+1} > r_{i_j}$。

将所有合法的子序列去重，$q$ 次查询，求字典序第 $k$ 小的子序列中所有元素之和。

两个子序列相同，当且仅当它们长度相同，且对应位置上的元素相同。

输入格式

第一行一个正整数 $n, q$。 第二行 $n$ 个正整数 $a_1,a_2,..., a_n$。 第三行 $n$ 个正整数 $r_1,r_2,..., r_n$。 接下来 $q$ 行，每行一个正整数 $k$，表示查询。 保证至少有 $k$ 个不同的合法子序列。

输出格式

$q$ 行，第 $i$ 行输出第 $i$ 次查询的答案。

样例输入

5 9
1 2 3 2 3
2 2 5 4 5
1
2
3
4
5
6
7
8
9

样例输出

1
3
6
4
2
4
7
5
3

样例解释

所有不同的子序列按字典序排列为：

1. 1
2. 1, 2
3. 1, 2, 3
4. 1, 3
5. 2
6. 2, 2
7. 2, 2, 3
8. 2, 3
9. 3

数据范围与提示

对于所有数据，有 $1 \leq n, q \leq 2 \times 10^5, 1 \leq a_i \leq n, i \leq r_i \leq n, 1 \leq k \leq 10^{18}$。

下发文件