Назовем перестановку \(p\) длины \(n\) антифибоначчиевой, если для всех \(i\) (\(3 \le i \le n\)) выполняется \(p_{i-2} + p_{i-1} \ne p_i\). Напомним, что перестановкой называется массив длины \(n\), содержащий каждое целое число от \(1\) до \(n\) ровно один раз.
Ваша задача — для заданного числа \(n\) вывести \(n\) различных антифибоначчиевых перестановок длины \(n\).
Выходные данные
Для каждого набора входных данных выведите \(n\) строк. Каждая строка должна содержать антифибоначчиеву перестановку длины \(n\). В каждом наборе входных данных каждая перестановка должна быть выведена не более одного раза.
Если существует несколько ответов, выведите любой из них. Можно показать, что всегда существует способ найти \(n\) различных антифибоначчиевых перестановок длины \(n\), соблюдая ограничения задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
3
|
4 1 3 2
1 2 4 3
3 4 1 2
2 4 1 3
3 2 1
1 3 2
3 1 2
|