17. Игра с числами

Бока и Жока остались в классе после уроков, и чтобы не терять время впустую, они решили сыграть в интересную игру.

Для начала они выписывают на доске $n$ чисел в ряд. На каждом шаге игрок может выбрать от одного до $m$ чисел из начала последовательности и стереть их. После этого игроку начисляется столько очков, сколько в сумме дают те числа, которые он стёр. Игра продолжается до тех пор, пока на доске все ещё есть числа.

Цель игры — получить в конце сумму очков, превосходящую сумму оппонента. Бока и Жока делают ходы поочерёдно, и Бока начинает первым. Оба игрока играют оптимально. Гарантируется что ничья невозможна.

Входные данные состоят из двух строк. В первой строке даны числа $n$ $\left(4 \leq n \leq 50000\right)$ и $m$ $\left(3 \leq m \leq 100\right)$. Во второй строке даны $n$ чисел — числа, записанные на доске. Каждое число во второй строке по модулю не превышает 1000.

Выведите 1, если победителем окажется Бока. В противном случае, выведите 0.