Game

Time limit2sMemory limit512 MB

Summary

For each starting size P, two players alternately take a number from a buffer that refills with later sequence elements, and we report Alice's score minus Bob's.

Level: Medium7 of 10
Topics: Greedy, Sorting, Game theory, Prefix sum
Solved: No attempts yet

Problem

Alice and Bob play the following game.

There is a sequence of $N$ positive integers numbered from $1$ to $N$ . Each element is at most $N$ , and equal values may appear more than once. At the start of a game, the first $P$ elements of the sequence form a multiset $S$ . Alice moves first, and the two players alternate turns. Each turn proceeds as follows:

The player to move chooses one number from $S$ , removes it, and adds its value to their own score. Both scores start at $0$ .
If the sequence still has an element that has not entered $S$ , the earliest such element is added to $S$ . That is, after the first removal the element with index $P+1$ is added, after the second removal the element with index $P+2$ is added, and so on. If the sequence is already exhausted, nothing is added.

Play continues until $S$ becomes empty. Each player tries to maximize their own final score. The result of a game is Alice's score minus Bob's score.

Write a program game that processes $K$ games played on one given starting sequence, where the games differ only in their starting sizes.

Input

The first line of the standard input contains two positive integers $N$ and $K$ , separated by a space.

The second line contains $N$ positive integers $a_1, a_2, \dots, a_N$ , separated by spaces, representing the elements of the given sequence.

The third line contains $K$ positive integers $p_1, p_2, \dots, p_K$ , separated by spaces. The $i$ -th game starts from the set $S$ built from the first $p_i$ elements of the sequence, where $i = 1, 2, \dots, K$ .

Output

Print $K$ lines to the standard output. The $i$ -th line contains a single integer, the result of the $i$ -th game. The games are numbered from $1$ to $K$ in the order given by the input.

Constraints

$1 \le N \le 100000$
$1 \le K \le 2000$
$K \le N$
$1 \le a_i \le N$ for every $i = 1, 2, \dots, N$
$1 \le p_i \le N$ for every $i = 1, 2, \dots, K$
In $10\%$ of the tests: $1 \le N \le 10$
In $30\%$ of the tests: $1 \le N \le 600$
In $50\%$ of the tests: $1 \le N \le 10000$ , $1 \le K \le 1000$

Hint

Each game lasts exactly $N$ moves. Alice takes the numbers on the odd-numbered turns, and Bob takes the numbers on the even-numbered turns. While arrivals remain, one new number enters $S$ after every turn, so $S$ always holds $P$ numbers at the start of a turn during that phase. Once arrivals run out, the rest of $S$ is removed in order until it is empty.

Examples2

Example 1
Input
```
5 2
2 4 2 3 5
4 3
```
Expected output
```
2
6
```
Example 2
Input
```
1 1
1
1
```
Expected output
```
1
```