Перехватив сообщение по открытому каналу связи, взломщица Ева узнала о том, что Алиса и Боб проводят время за интересной игрой, а ее даже не позвали! Возмущенная такой несправедливостью, она решила сорвать им игру. Сначала Ева хотела по привычной ей схеме перехватить фишку, но потом решила не мелочиться и стащила у ребят доску.
Играть одной ей было скучно, поэтому она захотела заняться художеством. Ева решила купить краски разных цветов и покрасить каждую клетку доски в один из цветов. Эстетическое чувство подсказывает ей, что будет некрасиво покрасить две клетки в один и тот же цвет в следующих трех случаях:
Если в таблице нет двух покрашенных в один цвет клеток, удовлетворяющих условиям выше, Ева сочтет покраску красивой.
Помогите Еве найти способ красиво покрасить доску, при котором ей нужно будет купить минимальное количество различных цветов.
В первой строке записано целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — количество строк на доске.
Во второй строке записано целое число $$$m$$$ ($$$2 \le m \le 10^6$$$) — количество столбцов на доске.
Гарантируется, что $$$n \times m \leq 10^6$$$.
В первой строке запишите целое число $$$k$$$ — минимальное количество различных цветов.
В каждой из следующих $$$n$$$ строк через пробел запишите $$$m$$$ целых чисел $$$c_{ij}$$$ ($$$1 \le c_{ij} \le k$$$) — цвет, в который следует покрасить клетку, находящуюся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца.
Покраска доски должна быть красивой. Если существует несколько покрасок, требующих минимального количества цветов, запишите в качестве ответа любую.
Баллы за каждую подзадачу, кроме первой, начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Первая подзадача содержит $$$14$$$ тестов, каждый из которых оценивается независимо в $$$1$$$ балл.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 14 | $$$2 \le n, m \le 5$$$ $$$n \times m \le 25$$$ | полная | |
| 2 | 13 | $$$2 \le n, m \le 100$$$ $$$n \times m \le 100$$$ | 1 | первая ошибка |
| 3 | 20 | $$$2 \le n, m \le 10\,000$$$ $$$n \times m \le 10\,000$$$ | 1, 2 | первая ошибка |
| 4 | 13 | $$$2 \le n, m \le 10^6$$$ $$$n \times m \le 10^6$$$ Для покраски потребуется не более двух цветов | первая ошибка | |
| 5 | 20 | $$$2 \le n \le 4$$$ $$$2 \le m \le 10^6$$$ $$$n \times m \le 10^6$$$ | первая ошибка | |
| 6 | 20 | нет | 1 – 5 | первая ошибка |
2 2
2 1 2 2 1
3 5
3 3 1 2 1 2 2 3 1 3 1 1 2 3 2 3
