Поликарп решил сгенерировать карту биомов для своей игры. Карта представляет собой матрицу, разбитую на клетки \(1 \times 1\). В каждой клетке карты должен находиться один из доступных биомов.
Каждый биом определяется двумя параметрами: температура (целое число от \(1\) до \(n\)) и влажность (целое число от \(1\) до \(m\)). Но, возможно, не для каждой комбинации температура/влажность доступен соответствующий биом.
Карта биомов должна быть сгенерирована по следующим правилам:
- каждая клетка карты принадлежит ровно одному биому;
- каждому доступному биому принадлежит хотя бы одна клетка карты;
- если две клетки карты являются соседними по стороне, и они принадлежат биомам с параметрами (\(t_1, h_1\)) и (\(t_2, h_2\)) соответственно, то должно выполняться равенство \(|t_1-t_2| + |h_1-h_2| = 1\);
- пусть количество доступных биомов равно \(k\). Ни количество строк, ни столбцов карты не должно превышать \(k\).
Помогите Поликарпу сгенерировать карту биомов, которая удовлетворяет всем вышеописанным условиям (или сообщите, что это невозможно).
Выходные данные
Для каждого набора входных данных выведите ответ в следующем формате:
- в единственной строке выведите \(-1\), если не существует карты удовлетворяющей всем условиям;
- иначе в первой строке выведите два целых числа \(h\) и \(w\) — количество строк и столбцов карты соответственно. В следующих \(h\) строках выведите по \(w\) целых чисел — идентификаторы биомов в соответствующих клетках поля.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3
0 2 5
0 1 0
3 5
0 3 4 9 11
1 5 0 10 12
0 6 7 0 0
2 2
2 0
0 5
1 2
13 37
|
1 3
5 2 1
2 8
11 9 4 3 5 1 5 6
12 10 9 4 3 5 6 7
-1
1 2
13 37
|