Игры с шишечками
Игры с шишечками
- Миша, а зачем ты каждый раз приносишь из лесу вместе с веточками так много шишечек? Ведь для выкладывания знаков арифметических действий тебе их хватило бы в пределах десятка, ну максимум двух…
- А мы с тобой, Маша, этими шишечками будем в игры играть до весны, а весной шишечки посадим, и из них вырастут новые ёлочки.
- А что за игра?
- Значит, правила такие: я раскладываю N кучек с шишечками, в каждой кучке – как повезёт, т.е. сколько сумею за один раз из мешочка на кучку высыпать. Далее будем брать шишечки по очереди, и ты при этом будешь всегда ходить первой. За один ход можно взять произвольное число шишечек из не менее одной, но не более чем из K кучек. Кто заберёт последнюю шишечку – тот и выиграл.
- Ух ты, как интересно! Давай быстрее Миша раскладывай – поиграем.
Ваша задача очень проста: определить, кто из них выиграет в очередной игре, если известно, что и Маша и Миша придерживаются в этой игре оптимальной выигрышной стратегии.
Giriş verilənləri
В первой строке задано натуральное число T - количество игр между Машей и Мишей – не более 100. Далее в T пар строк описаны сами игровые положения перед началом очередной игры: в первой строке каждой пары заданы натуральные N (1 ≤ N ≤ 10000) и K, а во второй через пробел описано количество шишечек S_i (0 ≤ S_i ≤ 2147483647) в каждой кучке.
Çıxış verilənləri
Для каждого тестового случая в отдельной строке выведите сообщение "Masha wins", если выиграет Маша или "Misha wins", если, соответственно, выиграет хитрый и мудрый медведь (ведь не просто так он уступал право первого хода Маше).
Nümunə
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
Misha wins Misha wins Masha wins