Задача E. Крестики-нолики ≡

Условие

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

Правила игры следующие: два игрока по очереди делают ходы на поле 3 × 3. Ход заключается в том, чтобы поставить в любую свободную клетку свой символ. Тот кто ходит первым ставит крестики, тот кто вторым — нолики. Выигрывает тот, кто первым сможет собрать в линию по вертикали, горизонтали или диагонали три своих символа. Если никто не смог этого сделать — объявляется ничья.

Преподаватель решил позволить Пете ходить первым, так как хочет эффектно рисовать на доске нолики, символизируя тем самым, что именно он думает о знаниях Пети по его предмету.

Формат входных данных

В первой строке записано одно целое число N — количество партий.

Протокол взаимодействия

Чтобы сделать ход ваша программа должна вывести "x y", где x — номер строки, y — номер столбца, куда Петя совершает ход.

На каждый свой ход программа жюри может вывести следующее:

 — "win" — если ход вашей программы стал выигрышным для Пети;

 — "draw" — если преподаватель не может сделать ход и объявлена ничья;

 — в первой строке "go", а во второй строке "x y" — ход преподавателя в соответствующую клетку;

 — в первой строке "lose", а во второй строке "x y" — если соответствующий ход преподавателя приводит его к победе;

Если ваша программа получила "win" или "draw", то сразу же начинается новая партия, кроме случая, когда текущая партия была последней.

Если ваша программа получила "lose", то она должна немедленно завершиться. На данном тесте ваше решение получит вердикт "Wrong answer".

Если ваша программа попытается сделать ход в уже занятую клетку, то это приведёт к получению вердикта "Presentation error".

Каждый ход должен заканчиваться символом перевода строки \n, а также необходимо выполнить очистку потока вывода:

Ограничения

1 ≤ N ≤ 1000

1 ≤ x, y ≤ 3

Описание системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов за каждый тест.

Пояснение к примерам

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

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

Примеры тестов

2

go
1 2

go
3 1

go
2 1

win

go
2 2

go
1 3

go
3 2

go
1 1

draw

2 2


1 3


2 3


3 3

3 3


1 2


3 1


2 1


2 3