P6294 [eJOI 2017] Game

Alice and Bob are ~~once again~~ playing a game. They have a sequence of $n$ positive integers, each $\le n$. The elements in the sequence are indexed from $1$ to $n$. The sequence may contain duplicate numbers. At the start of the game, there is a multiset $S$ containing the first $p$ elements of the sequence. The two players now begin the game, with Alice moving first. In each step: 1. The player chooses a number from $S$ and removes it from $S$, then adds the value of this removed number to their score (initially, both scores are zero). 2. The next number in the sequence (if any remain) is added to the multiset $S$ (if the sequence is already empty, skip this operation). That is, after the first removal from $S$, the $(p+1)$-th number of the sequence is added to $S$; after the second removal, the $(p+2)$-th number is added, and so on. The game continues until $S$ becomes empty. We assume both players are very smart (i.e., they always act to maximize their own benefit). The result of the game is defined as Alice's score minus Bob's score. Now, your task is to write a program to compute the results of $k$ games (all using the same given sequence).

The first line contains two positive integers $n,k$. The second line contains $n$ positive integers $a_1,a_2,...,a_n$, describing the initial sequence of the game. The third line contains $k$ positive integers $p_1,p_2,...,p_k$, where $p_i$ means that in the $i$-th game, $p=p_i$.

Output $k$ positive integers, one per line. The $i$-th positive integer indicates the result of the $i$-th game.

#### Explanation of Sample 1 The input specifies that you need to process $2$ games. The sequence is the same in both games, and only the initial multiset $S$ is different. In the first game it is $\{2, 4, 2, 3\}$, and in the second it is $\{2,4,2\}$. #### Constraints - For the first $10\%$ of the testdata, $1\le n\le 10$. - For the first $30\%$ of the testdata, $1\le n\le 600$. - For the first $50\%$ of the testdata, $1\le n\le 10^4,1\le k\le 10^3$. - For all testdata, $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]$. #### Notes The original problem is from: [eJOI2017](www.ejoi.org) Problem F. [Game](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_2/EN/game_statement-en.pdf). Translated by ChatGPT 5