题目描述

题目译自 eJOI2017 Problem F. Game

Alice 和 Bob 在玩如下的游戏：

有一个长度为 $N$ 的正整数序列，元素的值都小于等于 $N$。序列中元素的下标从 $1$ 到 $N$。在序列中可能存在相等的数字。在游戏最初有一个集合 $S$ 包含序列的前 $P$ 个元素。请注意 $S$ 是一个可重集合——它可能包含相等的元素。玩家轮流操作，Alice 先手。每次操作按如下方式进行：

1. 这轮操作的玩家先选择集合 $S$ 中的一个元素并从集合中删掉这个元素，这个玩家的分数就加上操作中选择的这个元素（初始时每个玩家的分数都为 $0$）。
2. 如果序列中还有数字，就把序列中下一个数字加到集合 $S$ 中（如果序列为空就跳过这个操作）。也就是说，在第一次拿走 $S$ 中的元素后，把下标为 $P+1$ 的数字加到集合 $S$ 中，在第二次拿走 $S$ 中的元素后，把下标为 $P+2$ 的数字加到集合 $S$ 中，以此类推。

游戏继续进行，直到 $S$ 变为空集。我们假设玩家都尽力最大化自己的得分。游戏的结果是 Bob 的得分减去 Alice 的得分。

写一个程序，给定初始序列，处理 $K$ 次游戏的结果。

输入格式

第一行两个正整数 $N,K$。

第二行 $N$ 个正整数 $a_1,a_2,\ldots,a_N$，表示给定的序列。

第三行 $K$ 个正整数 $p_1,p_2,\ldots,p_K$，第 $i$ 个数表示第 $i$ 次游戏中按照给定序列创建的最初的集合 $S$（取出前 $p_i$ 个元素）。

输出格式

输出 $K$ 行，每行包含一个整数，表示对应的游戏结果。第 $i$ 行输出第 $i$ 次游戏的结果。

5 2
2 4 2 3 5
4 3

2
6

数据范围与提示

对于所有数据，$1\le N\le 10^5,1\le K\le 2\times 10^3,K\le N,1\le a_i,p_i\le N$。

• 对于 $10\%$ 的数据，$1\le N\le 10$；
• 对于 $30\%$ 的数据，$1\le N\le 600$；
• 对于 $50\%$ 的数据，$1\le N\le 10^4,1\le K\le 10^3$。