Гра в закреслювання

Полоска паперу розділена на n клітин. Двоє гравців по черзі вибирають і закреслють рівно k пустих суміжних клітин. Виграє той, хто зробить останній хід. Обидва гравці дотримуються правильної стратегії. Дано ситуацію гри. Потрібно визначити, хто виграє.

Вхідні дані

У першому рядку містяться числа n і k (1 ≤ k ≤ n ≤ 40), у другому рядку n символів: латинська велика O - пуста клітинка, латинська велика X - закреслена клітинка.

Вихідні дані

Вивести одне число: 1 - якщо виграє той, хто зробить хід першим; 2 - якщо виграє другий; 0 - якщо хід зробити неможливо.

Приклади