В парламенте Берляндии n парламентариев, пронумерованных целыми числами от 1 до n. Так получилось, что все парламентарии с нечётными номерами — демократы, а с чётными — республиканцы.
Новый парламентский зал представляет собой прямоугольник из a × b кресел — a рядов по b кресел в каждом. Два кресла называются соседними, если они примыкают друг к другу по стороне. Например, для кресла номер 5 в ряду номер 2 соседями являются кресла с номерами 4 и 6 в этом ряду и кресла с номерами 5 в рядах 1 и 3. Таким образом, в общем случае у кресла четыре соседа, кроме кресел на границе зала.
Известно, что если два парламентария из одной партии сидят рядом, то они отвлекаются на партийные вопросы.
Напишите программу, которая предложит какой-нибудь способ рассадить парламентариев в зале так, чтобы не нашлось пары соседних парламентариев из одной партии.
Выходные данные
Выведите единственное число -1, если не существует способа рассадить всех парламентариев в зале требуемым образом.
Если решение существует, то выведите любое из них в виде a строк по b чисел в каждой. В j-й позиции i-й строки выведите номер парламентария, которого следует посадить в соответствующее кресло, или 0, если кресло следует оставить пустым. Если вариантов решения может быть несколько, разрешается вывести любой из них.
Примечание
Для первого тестового примера существует еще несколько вариантов ответа, например:
3 2
0 1,
а также
2 1
3 0.
Следующая рассадка
3 2
1 0
является некорректной, так как парламентарии с номерами 1 и 3 — оба из партии демократов — будут сидеть на соседних креслах.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 2
|
0 3
1 2
|
|
2
|
8 4 3
|
7 8 3
0 1 4
6 0 5
0 2 0
|
|
3
|
10 2 2
|
-1
|