Для геологической разведки перед добычей радия на плато Меридиана на орбиту Марса выведен специальный спутник, позволяющий измерять уровень радиоактивности на поверхности.

Представим плато как прямоугольник, состоящий из $$$n \times m$$$ единичных квадратов, обозначим $$$j$$$-й квадрат в $$$i$$$-м ряду как $$$(i, j)$$$.

В результате сканирования плато для каждого единичного квадрата был определён уровень радиоактивности. Уровень радиоактивности квадрата $$$(i, j)$$$ задаётся целым положительным числом $$$a_{ij}$$$. Точность измерений настолько велика, что все числа $$$a_{ij}$$$ различны. Единичный квадрат $$$(i, j)$$$ считается подходящим для добычи радия, если значение $$$a_{ij}$$$ является максимальным в $$$i$$$-й строке, а также максимальным в $$$j$$$-м столбце.

В процессе наблюдений было проведено $$$q$$$ последовательных уточнений уровня радиоактивности. А именно, $$$k$$$-е уточнение изменяло значение $$$a_{r_kc_k}$$$ на некоторое строго большее значение. При этом после каждого уточнения все значения $$$a_{ij}$$$ оставались различными.

Требуется написать программу, которая по заданным исходным значениям $$$a_{ij}$$$ и списку уточнений после каждого уточнения информации определяет количество подходящих для добычи радия единичных квадратов.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 25 & 1 \le n \cdot m \le 100, 1 \le q \le 100 & 0 \\ \hline 2 & 25 & 1 \le n \cdot m \le 5000, 1 \le q \le 5000 & 0, 1 \\ \hline 3 & 25 & 1 \le n, m \le 400, 1 \le q \le 200\,000 & 0, 1 \\ \hline 4 & 25 & 1 \le n \cdot m \le 200\,000, 1 \le q \le 200\,000 & 0, 1, 2, 3 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.

Одна телекоммуникационная компания планирует в скором будущем выпустить на рынок сразу два инновационных смартфона. Эти смартфоны будут называться «иннофон» и «иннофон плюс». Устройства уже полностью готовы к производству, и последняя задача, которую необходимо решить руководству компании, — выбрать оптимальную цену для каждого из смартфонов.

Аналитики компании провели исследование, в результате которого построили следующую модель. Всего есть $$$n$$$ потенциальных покупателей инновационных смартфонов. Для принятия решения $$$i$$$-й покупатель использует следующий алгоритм, характеризующийся двумя числами $$$a_i$$$ и $$$b_i$$$ ($$$a_i \geq b_i$$$):

• если цена на «иннофон плюс» не больше $$$a_i$$$, то он покупает «иннофон плюс»,
• иначе, если цена на «иннофон» не больше $$$b_i$$$, то он покупает «иннофон»,
• иначе он не покупает ничего.

Руководство компании хочет установить цены на «иннофон» и «иннофон плюс» таким образом, чтобы обе цены были целым числом, цена «иннофона» была не больше цены «иннофона плюс», и при этом суммарная стоимость проданных смартфонов была максимальна.

Требуется написать программу, которая находит максимально возможную суммарную стоимость проданных смартфонов.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 9 & n \le 100; b_i \le a_i \le 100 & 0 \\ \hline 2 & 10 & n \le 300 & 0, 1 \\ \hline 3 & 16 & n \le 3000 & 0, 1, 2 \\ \hline 4 & 11 & n \le 10^5; b_i = 0 & \\ \hline 5 & 16 & n \le 10^5; a_i = b_i & \\ \hline 6 & 7 & n \le 50\,000 & 0 - 3 \\ \hline 7 & 7 & n \le 75\,000 & 0 - 3, 6 \\ \hline 8 & 8 & n \le 100\,000 & 0 - 7 \\ \hline 9 & 8 & n \le 125\,000 & 0 - 8 \\ \hline 10 & 8 & n \le 150\,000 & 0 - 9 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.

Ученые в IT-компании разработали квантовый суперкомпьютер. Опытный образец, разработанный учеными, содержит $$$n \times m$$$ квантовых процессоров, организованных в виде сетки из $$$n$$$ строк и $$$m$$$ столбцов. Обозначим процессор в $$$j$$$-й ячейке $$$i$$$-й строки как $$$(i, j)$$$.

Ученые запустили квантовый суперкомпьютер, однако после окончания вычислений произошел сбой в электропитании, из-за чего часть процессоров оказалась повреждена. В распоряжении исследователей осталось всего лишь $$$k$$$ уцелевших процессоров.

Результат вычислений находится в памяти процессора $$$(1, 1)$$$, а устройство вывода подключено к процессору $$$(n, m)$$$. Для передачи информации от одного процессора к другому используется квантовая телепортация. Особенность квантовой телепортации заключается в том, что с увеличением расстояния возникает нестабильность, требующая дополнительной энергии. Поэтому чтобы обеспечить перенос информации от процессора $$$(x_i, y_i)$$$ к процессору $$$(x_j, y_j)$$$ требуется $$$2^{\max(|x_i - x_j|, |y_i - y_j|)}$$$ единиц энергии. Ученые хотят перенести информацию с процессора $$$(1, 1)$$$ на процессор $$$(n, m)$$$, затратив минимальное количество энергии. При этом можно использовать в качестве промежуточных другие уцелевшие процессоры. Использовать поврежденные процессоры нельзя.

Требуется написать программу, которая по описанию уцелевших процессоров определяет, каким образом необходимо передавать данные между процессорами, чтобы перенести информацию из процессора $$$(1, 1)$$$ в процессор $$$(n, m)$$$, потратив минимальное суммарное количество энергии.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 21 & 2 \le n, m, k \le 20 & 0 \\ \hline 2 & 13 & 2 \le n, m, k \le 500 & 0, 1 \\ \hline 3 & 33 & 2 \le n, m, k \le 10\,000; x_i \neq x_j; y_i \neq y_j & \\ \hline 4 & 33 & 2 \le n, m, k \le 10\,000 & 0 - 4 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.

Одной из важнейших задач современной информатики является моделирование биологических процессов. Недавно биологи обнаружили $$$n$$$ вирусов, каждому из которых был присвоен уникальный кодовый номер от $$$1$$$ до $$$n$$$. Вирус обладает возможностью встраиваться в клетки других организмов. Изначально в распоряжении ученых находятся $$$n$$$ клеток, пронумерованных от $$$1$$$ до $$$n$$$, при этом клетка с номером $$$i$$$ заражена вирусом $$$i$$$. Каждая клетка может быть заражена только одним вирусом.

Для каждой клетки был установлен уровень её восприимчивости к каждому из вирусов. А именно, для каждой клетки известен вирус, к которому она наиболее восприимчива, к какому из оставшихся вирусов она наиболее восприимчива, и так далее.

Зараженные вирусами клетки атакуют друг друга. Пусть клетка с номером $$$i$$$ сейчас заражена вирусом с номером $$$a$$$ и атакует клетку с номером $$$j$$$, которая заражена вирусом с номером $$$b$$$. Тогда, если клетка с номером $$$j$$$ является более восприимчивой к вирусу $$$a$$$, чем к вирусу $$$b$$$, то клетка с номером $$$j$$$ становится заражена вирусом $$$a$$$.

В эксперименте ученые помещают все $$$n$$$ клеток в замкнутую среду, в результате чего клетки могут атаковать друг друга произвольным образом. Эксперимент завершается, когда в результате таких атак ни для какой клетки не может измениться вирус, которым она заражена.

Ученые называют вирус с номером $$$i$$$ стабильным, если при любой последовательности атак клетками друг друга, приводящей к завершению эксперимента, останется хотя бы одна клетка, зараженная вирусом с номером $$$i$$$.

Ученые называют вирус с номером $$$i$$$ жизнеспособным, если существует такая последовательность атак клетками друг друга, приводящая к завершению эксперимента, после которой останется хотя бы одна клетка, зараженная вирусом с номером $$$i$$$.

Например, пусть есть два вируса, при этом клетка номер 1 наиболее восприимчива к вирусу номер 1, а клетка с номером 2 — наиболее восприимчива к вирусу номер 2. Тогда эксперимент завершается сразу: любая атака не приводит к изменению того, каким вирусом заражена клетка. Таким образом оба вируса являются стабильными и жизнеспособными.

Пусть теперь есть два вируса, но клетка с номером 1 наиболее восприимчива к вирусу с номером 2, а клетка с номером 2 — к вирусу с номером 1. Тогда эксперимент завершается после любой атаки одной клеткой другой. Возможны два сценария. В первом сценарии клетка 1 атакует клетку 2, обе клетки становятся заражены вирусом 1. Во втором сценарии клетка 2 атакует клетку 1, после этого обе клетки становятся заражены вирусом 2. Таким образом, стабильных вирусов нет, но оба вируса являются жизнеспособными.

Наконец, пусть есть два вируса, и обе клетки более восприимчивы к вирусу с номером 1. Тогда атака клеткой 2 клетки 1 не приводит к изменению вируса, которым она заражена, а если клетка 1 атакует клетку 2, то вторая клетка становится зараженной вирусом 1. Следовательно эксперимент завершится после атаки клетки 1 клеткой 2, вирус 1 является стабильным и жизнеспособным, а вирус 2 не обладает ни тем, ни другим свойством.

Ученым необходимо отвечать на два типа вопросов, какие вирусы являются стабильными и какие вирусы являются жизнеспособными.

Требуется написать программу, которая по описанию клеток и типу вопроса определяет все стабильные, либо все жизнеспособные вирусы.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 11 & 1 \le n \le 5; p = 1 & \\ \hline 2 & 21 & 1 \le n \le 500; p = 1 & 1 \\ \hline 3 & 22 & 1 \le n \le 5 & 0, 1 \\ \hline 4 & 31 & 1 \le n \le 50 & 0 - 3 \\ \hline 5 & 15 & 1 \le n \le 500 & 0 - 4 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.