Нечетный ним

문제

Миша и Глеб очень любят знаменитую игру ним. Напомним вкратце её правила:

• На столе лежат N кучек камней, в кучке с номером i содержится a_i камней.
• Играют два игрока, игроки ходят по очереди, на каждом ходу игрок обязан выбрать любую непустую кучку и убрать из неё любое ненулевое количество камней.
• Проигрывает тот, кто не может сделать ход.

Наши герои играют в эту игру уже так давно, что обнаружили выигрышную стратегию, и теперь могут определить победителя просто взглянув на стол. Поняв, что данная игра утратила свою новизну, они переключились на ним в поддавки, который отличается от оригинального только тем, что игрок, который не может сделать ход, объявляется победителем.

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

Тогда было принято решение еще усложнить правила — теперь разрешается брать только любое нечетное количество камней. На этот раз Витя не смог обнаружить стратегию и помешать двум друзьям, поэтому он обратился за помощью к вам. Напишите программу, определяющую победителя в игре ним, если разрешается брать из кучки только нечетное количество камней. На всякий случай научитесь также определять победителя для нима в поддавки, в котором также можно брать только нечетное количество камней — Витя подозревает что именно эта игра станет для Глеба и Миши следующей.

Миша всегда ходит первым.

입력

В первой строке входного файла записано единственное число N, 1 ⩽ N ⩽ 10⁵. Следующая строка содержит N чисел a_i, 1 ⩽ a_i ⩽ 10⁹.

출력

На первой строке выведите имя победителя в том случае, если проигрывает тот, кто не может сделать ход. Во второй строке выведите имя победителя в том случае, если тот, кто не может сделать ход, выигрывает.

2
1 2

Misha
Gleb