게임

Alice와 Bob이 다음 게임을 한다.

$1$부터 $N$까지 번호가 매겨진 $N$개의 양의 정수 수열이 주어진다. 각 원소는 $N$ 이하이며 같은 값이 여러 번 나올 수 있다. 게임이 시작되면 수열의 앞 $P$개 원소로 다중집합 $S$를 만든다. Alice가 먼저 움직이며 두 사람은 번갈아 둔다. 각 차례는 다음과 같이 진행된다.

1. 차례인 사람은 $S$에서 수 하나를 골라 꺼내고 그 값을 자신의 점수에 더한다. 두 사람의 점수는 처음에 모두 $0$이다.
2. 수열에 아직 들어오지 않은 수가 남았다면 그중 가장 앞선 수 하나를 $S$에 넣는다. 즉 첫 번째로 꺼낸 뒤에는 $P+1$번 원소가 들어오고, 두 번째로 꺼낸 뒤에는 $P+2$번 원소가 들어오는 식이다. 수열이 이미 비었다면 아무것도 넣지 않는다.

$S$가 빌 때까지 차례를 반복한다. 두 사람 모두 자신의 최종 점수가 가장 커지도록 둔다고 가정한다. 게임의 결과는 Alice의 점수에서 Bob의 점수를 뺀 값이다.

주어진 수열에 대해 시작 크기만 다른 $K$개의 게임을 처리하는 프로그램 game을 작성하라.

표준 입력의 첫 줄에는 두 양의 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

둘째 줄에는 수열을 나타내는 $N$개의 양의 정수 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다.

셋째 줄에는 $K$개의 양의 정수 $p_1, p_2, \dots, p_K$가 공백으로 구분되어 주어진다. $i$번째 게임은 수열의 앞 $p_i$개 원소로 만든 $S$에서 시작한다. 여기서 $i = 1, 2, \dots, K$이다.

표준 출력에 $K$줄을 출력한다. $i$번째 줄에는 $i$번째 게임의 결과를 나타내는 정수 하나를 출력한다. 게임 번호는 입력에 주어진 순서대로 $1$부터 $K$까지 매긴다.

• $1 \le N \le 100000$
• $1 \le K \le 2000$
• $K \le N$
• 모든 $i = 1, 2, \dots, N$에 대해 $1 \le a_i \le N$
• 모든 $i = 1, 2, \dots, K$에 대해 $1 \le p_i \le N$
• 테스트의 $10\%$에서는 $1 \le N \le 10$
• 테스트의 $30\%$에서는 $1 \le N \le 600$
• 테스트의 $50\%$에서는 $1 \le N \le 10000$, $1 \le K \le 1000$

각 게임은 정확히 $N$번 움직이며 끝난다. Alice는 홀수 번째 차례에, Bob은 짝수 번째 차례에 수를 가져간다. 들어올 수가 남아 있는 동안에는 매 차례가 끝난 뒤 새 수 하나가 $S$에 들어오므로, 그 구간에서는 차례를 시작할 때 $S$가 항상 $P$개의 원소를 가진다. 들어올 수가 떨어진 뒤에는 남은 $S$를 순서대로 꺼내며 끝낸다.