ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1512. Зиниум

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Зиниум – чудо нашего мира, а может быть, и всех миров. Найденный в конце XIX века при раскопках древнеримских поселений на территории современной Албании, Зиниум принадлежал самому Юлию Цезарю и был утрачен им в его последнем походе.

Задача

Артефакт представляет собой шахматную доску размером N*N клеток. Клетка в левом нижнем её углу имеет координаты (1, 1), а клетка в правом верхнем углу – координаты (N, N). По легенде, если на доске расставить N ферзей таким образом, что ни один из них не будет атаковать другого, то освобождённая энергия Зиниума изменит мир до неузнаваемости. Реки повернутся вспять, небо упадёт на землю, люди научатся называть вещи своими именами... Может быть, даже Петя Великолепный примет участие в очередном контесте Timus Top Coders. А может быть, и нет. Самое время проверить.

Исходные данные

Единственная строка содержит целое число N (4 ≤ N ≤ 100000).

Результат

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

Пример

исходные данныерезультат
8
1 5
2 1
3 8
4 4
5 2
6 7
7 3
8 6

Замечания

Два ферзя атакуют друг друга, если находятся в клетках, расположенных одной и той же горизонтали, вертикали или диагонали.
Автор задачи: Илья Гребнов, Никита Рыбак, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge