题目描述
给定一个长度为 $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, 3
- 2
- 2, 2
- 2, 2, 3
- 2, 3
- 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}$。