Задача №112447. Мутузов против Поналеона
Гений состоит в умении отличать трудное от невозможного.
О нет! Безрассудный Поналеон Бопанард напал на Екатеринбург, в котором совсем недавно прошла Всероссийская олимпиада школьников по информатике и скоро пройдёт Международная студенческая олимпиада по программированию. Коварный император хочет захватить лучших программистов, чтобы те помогли ему составить расписания выпечки багетов.
Но на помощь программистам уже спешит Химаил Мутузов, готовый сражаться во имя программирования до последнего!
И вот двое соперников встретились на поле брани. Поле представляет из себя прямоугольник размером \(N \times M\), разбитый на клеточки. Теперь каждому полководцу нужно выставить на поле как можно больше своих войск. Для честности Бопанард и Химаил договорились ставить войска по очереди.
Неожиданно выяснилось, что полководцы могут ставить свои войска не во все клетки. Поналеон не вышел ростом, поэтому может ставить войска только на строки, не бо́льшие \(K\)-ой. Мутузов же был ранен в одном из сражений и потерял левый глаз, поэтому он может ставить войска только на правую половину поля (столбцы нумеруются от \(1\) до \(M\) слева направо).
Также Поналеона иногда отвлекает пришедшая невовремя Фожезина, и в таком случае Поналеон вынужденно пропускает ход.
Вам предстоит помочь Химаилу Мутузову расставить войска. Да и что греха таить, он просто переложил вам на плечи всю расстановку войск, и теперь это — ваша головная боль.
При запуске решения на вход подаются три строки.
Первая из них содержит два целых числа \(N\) и \(M\) — размеры поля, на котором будет происходить сражение (\(1 \leq N, M \leq 100\)). Гарантируется, что \(M\) чётное. В следующей строке содержится единственное целое число \(K\) — номер наибольшей строки, в которую Поналеон может ставить войска (\(0 \leq K \leq N\)). В следующей строке вводится слово «Mutuzov», если первым войско на поле будет ставить Мутузов, и «Ponaleon», если первым войско на поле будет ставить Поналеон.
Для каждого хода Мутузова выполните следующие действия:
Для занятия клетки с координатами \((i, j)\) выведите через пробел числа \(i\) и \(j\). Занимаемая клетка обязательно должна быть пустой, то есть в ней не должно быть ни войска Мутузова, ни войска Поналеона.
Для каждого хода Поналеона на вход подаётся:
- Слово amour, если Поналеон вынужден пропустить этот ход.
- Слово guerre, если Поналеон ставит войско. В этом случае после слова в этой же строке на вход подаются два целых числа \(i\) и \(j\) — координаты занимаемой войском Поналеона клетки. Гарантируется, что \(1 \leq i \leq K\), \(1 \leq j \leq M\), и что клетка \((i, j)\) ещё не занималась ни одним войском.
Если после какого-то хода вы считаете, что больше ни одно войско Мутузов поставить не сможет, выведите строку 0 0. После этого ваша программа должна завершиться.
1 2 1 Mutuzov
1 2 0 0
2 2 2 Ponaleon guerre 2 1 guerre 1 1
2 2 1 2 0 0
4 2 1 Ponaleon guerre 1 2 amour guerre 1 1
2 2 3 2 4 2 0 0
В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.