Алиса очень любит бросать камни в море и наблюдать, как красиво вокруг них распространяются волны. Девочка настолько очарована этим процессом, что решила запечатлеть процесс распространения волн на своих рисунках.
Представим море как бесконечное поле, состоящее из клеток. На рисунках ниже клетка, в которую был брошен камень, обозначена буквой «К». Брошенный в воду камень, разумеется, создает вокруг себя волны: ровно через одну секунду после того, как камень был брошен, в четырех соседних по стороне клетках образуются волны. На рисунках ниже клетки, в которых образовались волны, обозначены черным цветом.
На этом распространение волн не заканчивается. Каждую секунду рисунок волн изменяется следующим образом: каждая черная клетка становится белой, а ее четыре соседние по стороне клетки становятся черными. На втором рисунке ниже изображена картина волн спустя две секунды после броска камня.
Рисунок 1. Распространение волн Процесс распространения волн продолжается бесконечно, и это очень радует Алису. Рисунок моря спустя $$$T$$$ после броска камня представить в своем воображении достаточно сложно. А вот посчитать количеств волн, изображенных черными клетками на рисунке через $$$T$$$ секунд после бросания камня, достаточно легко — так считает Алиса. Убедитесь в этом и вы.
В единственной строке записано целое число $$$T$$$ ($$$1 \le T \le 2 \cdot 10^9$$$) — время в секундах, прошедшее после броска камня.
Выведите одно число — количество черных клеток на рисунке волн через $$$T$$$ секунд после броска камня.
Помимо тестов из условия данная задача содержит $$$25$$$ тестов, каждый из которых оценивается независимо в $$$4$$$ балла.
1
4
2
9
Картина волн через одну и две секунды после броска камня изображена выше в условии задачи.
Обратите внимание, что ответ может получиться достаточно большим, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
Перехватив сообщение по открытому каналу связи, взломщица Ева узнала о том, что Алиса и Боб проводят время за интересной игрой, а ее даже не позвали! Возмущенная такой несправедливостью, она решила сорвать им игру. Сначала Ева хотела по привычной ей схеме перехватить фишку, но потом решила не мелочиться и стащила у ребят доску.
Играть одной ей было скучно, поэтому она захотела заняться художеством. Ева решила купить краски разных цветов и покрасить каждую клетку доски в один из цветов. Эстетическое чувство подсказывает ей, что будет некрасиво покрасить две клетки в один и тот же цвет в следующих трех случаях:
- Две клетки имеют соседнюю сторону.
- Одна из клеток является первой, а вторая — последней в одной строке.
- Одна из клеток является верхней, а вторая — нижней в одном столбце.
Если в таблице нет двух покрашенных в один цвет клеток, удовлетворяющих условиям выше, Ева сочтет покраску красивой.
Помогите Еве найти способ красиво покрасить доску, при котором ей нужно будет купить минимальное количество различных цветов.
В первой строке записано целое число $$$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