Московская олимпиада по информатике

на сайте www.olympiads.ru

Московская городская олимпиада школьников по информатике, 2005/06 учебный год
при поддержке компании

Задача E.

Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из 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).

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

В выходной файл ваша программа должна печатать следующие строки чисел:

K1	X1,1	X1,2	...	X1,m1
K2	X2,1	X2,2	...	X2,m2
...	...	...	...	...
Ke	Xe,1	Xe,2	...	Xe,me

где K_i - это число ходов, которые должны сделать телезрители, а X_i,1 ... X_i,mi - номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все K_i должны удовлетворять условию 2N≤K_i≤10000 и все K_i должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать K_i ходов, Дэвид должен убирать хотя бы одну картинку. Каждое K_i должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.

Пример

3

8 4 6
13 9
10 7 1
7 8
11 3 5