Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из N столбцов и N строк, в каждой клетке которого находится какая-нибудь картинка, появляется на экране телевизора. Пусть все картинки пронумерованы следующим образом:
| 1 |
2 |
… |
N |
| N+1 |
N+2 |
… |
2*N |
| : |
: |
… |
: |
| N*(N–1)+1 |
N*(N–1)+2 |
… |
N*N |
Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).
Дэвиду приходится довольно часто повторять этот трюк, и, чтобы не ошибиться, он попросил написать программу, которая будет ему сообщать, сколько ходов должны делать телезрители, и какие картинки нужно убирать. Напишите такую программу.
Входные данные
Во входном файле записано одно число N — размер квадрата (2<=N<=100).
Выходные данные
В выходной файл ваша программа должна печатать следующие строки чисел:
K
1 X
1,1 X
1,2 … X
1,m1
K
2 X
2,1 X
2,2 … X
2,m2
…
K
e X
e,1 X
e,.2 … X
e,me
где K
i — это число ходов, которые должны сделать телезрители, а X
i,1 … X
i,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все K
i должны удовлетворять условию 2N<=K
i<=10000 и все K
i должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать K
i ходов, Дэвид должен убирать хотя бы одну картинку. Каждое K
i должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
7 1 3 7 9
9 2 4 6 8
|