D. Painting
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Мити есть прямоугольный клетчатый холст, который может быть представлен в виде таблицы размера $$$n \times m$$$, и $$$k$$$ роботов. Пронумеруем строки таблицы от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — от $$$1$$$ до $$$m$$$ слева направо. Клетка $$$(x, y)$$$ лежит на пересечении строки номер $$$x$$$ и столбца номер $$$y$$$.

Изначально все клетки таблицы покрашены в белый цвет, который имеет номер $$$0$$$. Робот номер $$$i$$$ заправлен краской с цветом номер $$$i$$$ ($$$1 \le i \le k$$$). Для каждого робота Митя выбрал подпрямоугольник холста, который задается четырьмя целыми числами $$$x_{i, 1}$$$, $$$y_{i, 1}$$$, $$$x_{i, 2}$$$ и $$$y_{i, 2}$$$ и содержит все клетки $$$(x, y)$$$, такие что $$$x_{i, 1} \le x \le x_{i, 2}$$$ и $$$y_{i, 1} \le y \le y_{i, 2}$$$ ($$$1 \le x_{i, 1} \le x_{i, 2} \le n$$$, $$$1 \le y_{i, 1} \le y_{i, 2} \le m$$$). После этого роботы друг за другом по одному разу в случайном порядке покрасили свой прямоугольник в свой цвет. При покраске робот изменяет цвет всех клеток на прямоугольнике на новый цвет. При этом старые цвета клеток полностью заменяются на новый и уже никак не могут быть восстановлены.

На следующий день холст увидел Леша. Он заметил, что в каждый цвет от $$$1$$$ до $$$k$$$ покрашена хотя бы одна клетка. И ему стало интересно, какие прямоугольники Митя назначил каждому роботу. А именно его интересует, мог ли Митя назначить каждому роботу прямоугольник таким образом, чтобы существовал порядок роботов, при котором получилась бы такая покраска холста. И если Митя мог выбрать такие прямоугольники, Лешу интересует, единственным ли образом он мог это сделать. Два способа считаются различными, если существует робот, которому в этих способах назначены различные прямоугольники. Два прямоугольника считаются различными, если у них не совпадает хотя бы одна из четырех координат $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ или $$$y_2$$$.

Входные данные

В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — высота и ширина холста, количество роботов ($$$1 \le n, m \le 2\,000$$$; $$$1 \le k \le 1\,000$$$).

В следующих $$$n$$$ строках даны по $$$m$$$ целых чисел $$$c_{ij}$$$ — цвета клеток таблицы, задающей холст ($$$0 \le c_{ij} \le k$$$).

Гарантируется, что для каждого цвета от $$$1$$$ до $$$k$$$ существует хотя бы одна клетка, покрашенная в него.

Выходные данные

Если не существует способа, которым Митя мог бы назначить роботам прямоугольники, чтобы существовал порядок роботов, при котором получилась бы такая покраска, выведите «No solution».

Если существует единственный способ, в первой строке выведите «Single solution». В следующих $$$k$$$ строках выведите по четыре целых числа $$$x_{i, 1}$$$, $$$y_{i, 1}$$$, $$$x_{i, 2}$$$ и $$$y_{i, 2}$$$, задающие прямоугольник для $$$i$$$-го робота ($$$1 \le x_{i, 1} \le x_{i, 2} \le n$$$, $$$1 \le y_{i, 1} \le y_{i, 2} \le m$$$). И в последней строке выведите перестановку чисел от $$$1$$$ до $$$k$$$ — порядок работы роботов, при котором бы получилась такая расскраска.

Если способов больше одного, в первой строке выведите «Multiple solutions». В следующей строке выведите «First». В следующих строках выведите описание первого способа в том же формате, как и в предыдущем абзаце. В следующей строке выведите «Second». И в следующих строках выведите описание второго способа. Первый и второй способы должны различаться. Если существует больше двух различных способов, вы можете вывести любые два различных.

Система оценки
ПодзадачаБаллыДополнительные ограничения
15$$$k = 1$$$; $$$n, m \le 300$$$
25$$$k \le 2$$$; $$$n, m \le 300$$$
310$$$k \le 5$$$; $$$n, m \le 300$$$
425$$$n = 1$$$
525$$$n, m, k \le 300$$$
630без дополнительных ограничений
Примеры
Входные данные
3 4 3
0 3 3 0
1 3 2 1
1 1 2 1
Выходные данные
Single solution
2 1 3 4
2 3 3 3
1 2 2 3
1 3 2
Входные данные
2 2 2
1 2
2 1
Выходные данные
No solution
Входные данные
2 1 2
2
1
Выходные данные
Multiple solutions
First
2 1 2 1
1 1 2 1
2 1
Second
1 1 2 1
1 1 1 1
1 2
Входные данные
2 3 3
0 3 0
2 0 1
Выходные данные
Single solution
2 3 2 3
2 1 2 1
1 2 1 2
1 2 3