Игра
Алиса и Боб играют в следующую игру:
У них есть последовательность из n положительных целых чисел, каждое из которых не превышает n. Элементы этой последовательности пронумерованы от 1 до n. В последовательности могут встречаться одинаковые числа. В начале игры формируется множество s, содержащее первые p элементов последовательности. Обратите внимание, что s может быть мультимножеством, то есть содержать повторяющиеся элементы. Игроки ходят по очереди, начиная с Алисы. Каждый ход включает следующие действия:
Игрок, чей ход, выбирает одно число из множества s и удаляет его, добавляя его значение к своему счету (изначально счет обоих игроков равен 0).
Следующее число в последовательности, если оно еще есть, добавляется в множество s (если последовательность уже исчерпана, это действие пропускается). Это значит, что после первого взятия из s в него добавляется число с индексом p + 1, после второго - число с индексом p + 2 и так далее.
Игра продолжается до тех пор, пока множество s не станет пустым. Предполагается, что каждый игрок стремится максимизировать свой счет. Результат игры определяется как разность между очками Алисы и очками Боба.
Напишите программу game, которая должна обработать k игр на заданной начальной последовательности.
Входные данные
На первой строке вводятся два разделенных пробелом положительных целых числа N и K.
Вторая строка содержит N разделенных пробелом положительных целых чисел a1, a2, …, aN, представляющих элементы данной последовательности.
Третья строка содержит K разделенных пробелом положительных целых чисел p1, p2, ..., pK, каждое из которых определяет начальное множество S, сформированное из первых pi элементов последовательности для i-й игры, где i = 1, 2, ..., K.
Выходные данные
Программа должна вывести в стандартный вывод K строк, каждая из которых содержит одно целое число - результат соответствующей игры. Строка номер i должна содержать результат игры номер i (игры нумеруются от 1 до K по входным данным).
Ограничения
1 ≤ N ≤ 100 000
1 ≤ K ≤ 2 000
K ≤ N
1 ≤ a[i] ≤ N для i = 1, 2, …, N
1 ≤ p[i] ≤ N для i = 1, 2, …, K