题目描述

Alice 和 Bob 又双叒叕 在玩游戏。

他们有一个由 $n$ 个 $\le n$ 的正整数组成的序列。序列中的元素被从 $1$ 到 $n$ 标号。序列中可能存在相同的数字。游戏开始时有一个可重集 $S$ ，包含了序列的前 $p$ 个元素。两人现在开始了游戏，Alice 先手。每一步游戏：

1. 玩家选择一个 $S$ 中的数并将其从 $S$ 中取出，然后将自己的分数加上这个取出的数的值（一开始两人的分数都为零）。
2. 序列中的下一个数字（如果还有剩余）将会被添加到集合 $S$ 中（如果序列已经为空，则跳过此操作）。也就是说，从 $S$ 中取出第一个后，将序列的第 $p+1$ 个数字添加到集合中，在第二个之后，将序列的第 $p+2$ 个数字添加到集合中，以此类推。

游戏进行直到 $S$ 为空为止。我们假设两个玩家都非常聪明（即总是使自己利益最大化）。游戏的结果为 Alice 的分数减去 Bob 的分数。

现在，你的任务是写一个程序，计算 $k$ 个（给定序列相同的）游戏的结果。

输入格式

第一行，两个正整数 $n,k$。

第二行，$n$ 个正整数 $a_1,a_2,...,a_n$，描述游戏开始的序列。

第三行，$k$ 个正整数 $p_1,p_2,...,p_k$，$p_i$ 表示第 $i$ 次游戏，有 $p=p_i$ 。

输出格式

输出包含 $k$ 个正整数，一行一个。

第 $i$ 个正整数表示第 $i$ 次游戏的结果。

5 2
2 4 2 3 5
4 3

2
6

提示

样例 1 解释

输入确定了你需要处理 $2$ 个游戏。这两个游戏中的序列是相同的，至是开始时的可重集 $S$ 不同。第一个游戏为 $\{2, 4, 2, 3\}$ ，第二个为 $\{2,4,2\}$ 。

数据规模与约定

• 对于前 $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$。
• 对于所有数据，保证 $1\le n\le 10^5,1\le k\le 2\times 10^3,k\le n,a_i\in[1,n],p_i\in[1,n]$。

说明

原题来自： eJOI2017 Problem F. Game