Вступление
Зиниум чудо нашего мира, а может быть, и всех миров. Найденный в конце 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