eolymp
bolt
Try our new interface for solving problems
Məsələlər

Игры с шишечками

Игры с шишечками

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

- Миша, а зачем ты каждый раз приносишь из лесу вместе с веточками так много шишечек? Ведь для выкладывания знаков арифметических действий тебе их хватило бы в пределах десятка, ну максимум двух…

- А мы с тобой, Маша, этими шишечками будем в игры играть до весны, а весной шишечки посадим, и из них вырастут новые ёлочки.

- А что за игра?

- Значит, правила такие: я раскладываю N кучек с шишечками, в каждой кучке – как повезёт, т.е. сколько сумею за один раз из мешочка на кучку высыпать. Далее будем брать шишечки по очереди, и ты при этом будешь всегда ходить первой. За один ход можно взять произвольное число шишечек из не менее одной, но не более чем из K кучек. Кто заберёт последнюю шишечку – тот и выиграл.

- Ух ты, как интересно! Давай быстрее Миша раскладывай – поиграем.

Ваша задача очень проста: определить, кто из них выиграет в очередной игре, если известно, что и Маша и Миша придерживаются в этой игре оптимальной выигрышной стратегии.

Giriş verilənləri

В первой строке задано натуральное число T - количество игр между Машей и Мишей – не более 100. Далее в T пар строк описаны сами игровые положения перед началом очередной игры: в первой строке каждой пары заданы натуральные N (1N10000) и K, а во второй через пробел описано количество шишечек S_i (0S_i2147483647) в каждой кучке.

Çıxış verilənləri

Для каждого тестового случая в отдельной строке выведите сообщение "Masha wins", если выиграет Маша или "Misha wins", если, соответственно, выиграет хитрый и мудрый медведь (ведь не просто так он уступал право первого хода Маше).

Nümunə

Giriş verilənləri #1
3
15 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1
4 12 8
3 2
23 12 8
Çıxış verilənləri #1
Misha wins
Misha wins
Masha wins
Mənbə Командный Кубок Украины 2011 - школьники - тур 1