eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Ігри з шишечками

Ігри з шишечками

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

- А ми з тобою, Маша, цими шишечками будемо в ігри грати до весни, а весною шишечки посадимо, і з них виростуть нові ялинки.

- А що за гра?

- Значить, правила такі: я розкладаю N кучок з шишечками, у кожній купці – як повезе, тобто скільки зумію за один раз з мішечка на купку висипати. Далі будемо брати шишечки по черзі, і ти при цьому будеш завжди ходити першою. За один хід можна взяти довільну кількість шишечок не менше ніж з однієї, але не більше ніж з K купок. Хто забере останню шишечку – той і виграв.

- Ух ти, як цікаво! Давай Мишко швидше розкладай – пограємо.

Ваше завдання дуже просте: визначити, хто з них виграє у черговій грі, якщо відомо, що і Маша і Мишко дотримуються у цій грі оптимальної виграшної стратегії.

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #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
Вихідні дані #1
Misha wins
Misha wins
Masha wins
Джерело Командний Кубок України 2011 - школярі - тур 1