У Мити есть прямоугольный клетчатый холст, который может быть представлен в виде таблицы размера $$$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». И в следующих строках выведите описание второго способа. Первый и второй способы должны различаться. Если существует больше двух различных способов, вы можете вывести любые два различных.
| Подзадача | Баллы | Дополнительные ограничения |
| 1 | 5 | $$$k = 1$$$; $$$n, m \le 300$$$ |
| 2 | 5 | $$$k \le 2$$$; $$$n, m \le 300$$$ |
| 3 | 10 | $$$k \le 5$$$; $$$n, m \le 300$$$ |
| 4 | 25 | $$$n = 1$$$ |
| 5 | 25 | $$$n, m, k \le 300$$$ |
| 6 | 30 | без дополнительных ограничений |
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
| Название |
|---|


