В Японии очень популярны старые настольные игры на логику. Одна из таких игр проводится на доске размером $$$n \times m$$$.

В каждой позиции $$$(i, j)$$$, то есть на пересечении $$$i$$$-й сверху строки и $$$j$$$-го слева столбца, может находиться произвольное число фишек, которое мы обозначим за $$$a_{i, j}$$$. Правила самой игры довольно сложные: сложнее, чем шахматы, Го и Сёги, поэтому мы их не будем тут описывать целиком. Однако даже к стартовой расстановке фишек есть требования, про которые и будет эта задача.

Первое правило звучит следующим образом: к началу игры для любых двух соседних по стороне клеток суммарное число фишек в них должно быть нечётным. Более формально, если выполняется $$$|i_1-i_1| + |j_1-j_2| = 1$$$, то должно выполняться условие, что $$$a_{i_1, j_1} + a_{i_2, j_2}$$$ — нечётное число.

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

• чем меньше суммарное число фишек на поле после его действий;
• а при равенстве общего числа фишек — чем лексикографически меньше итоговая матрица $$$a_{i, j}$$$.

Напомним, что матрица $$$X$$$ лексикографически меньше матрицы $$$Y$$$, если после записи каждой из матриц в одну строку (по строкам, сначала выписав первую, затем вторую, и так далее), в первой позиции, где они различаются, в записи матрицы $$$X$$$ стоит меньшее число.

Требуется добиться выполнения требуемого правила, добившись наиболее выгодной для первого игрока стартовой позиции. После внесения изменений выведите итоговую таблицу значений $$$a_{i, j}$$$.

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

В Японии относительно недавно получила распространение школа стринг-арта: искусства, где изображения создаются на доске путем перевязывания нитей между вколотыми в нее гвоздиками.

Начинающий японский художник рисует абстрактную картину на $$$n$$$ гвоздиках, занумерованных от $$$1$$$ до $$$n$$$ в порядке их расположения на доске слева направо. Для каждого гвоздика известны его координаты на доске: $$$i$$$-й гвоздик расположен в позиции $$$(x_i, y_i)$$$, причем $$$x_1 \le x_2 \le \ldots \le x_n$$$.

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

• Если какая-то нить последний раз была привязана к гвоздику номер $$$i$$$, то затем ее можно привязать только к гвоздику с номером $$$ \gt i$$$. Иными словами, последовательность узлов на любой нити должна иметь строго возрастающие номера гвоздиков.
• Каждый гвоздик должен быть использован хотя бы один раз, то есть для любого $$$i$$$ существует либо узел первой нити на $$$i$$$-м гвоздике, либо узел второй нити, либо обеих.
• Суммарная потраченная длина нитей должна быть как можно меньше.

Расстояние между гвоздиками $$$i$$$ и $$$j$$$ равно $$$\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$$. Суммарная длина используемых нитей равна сумме расстояний между их соседними узлами. При этом каждая нить может быть привязана на произвольное число гвоздиков, и последние гвоздики двух нитей не обязаны совпадать.

Определите оптимальную основу для стринг-арт рисунка, для которой выполняются все поставленные условия.

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

В Японии есть огромное число традиционных способов приготовить одни и те же ингредиенты. Будем считать, что всего есть $$$n$$$ различных способов приготовления, пронумерованных от $$$1$$$ до $$$n$$$, и $$$m$$$ традиционных ингредиентов, пронумерованных от $$$1$$$ до $$$m$$$.

Известный шеф-повар устраивает мастер-класс и собирается приготовить ровно $$$a_{i, j}$$$ блюд, используя $$$i$$$-й способ готовки и $$$j$$$-й ингредиент как основной. Соответственно, суммарное число приготовленных блюд будет равно $$$A = \sum\limits_{i=1}^n \sum\limits_{j=1}^m a_{i, j}$$$.

Два известных кулинарных критика планируют посетить мастер-класс, и шеф-повар заранее планирует, какие $$$k$$$ из этих $$$A$$$ блюд он предоставит им на дегустацию. Разумеется, у критиков есть строгие правила, которые они выдвигают к выбранному набору блюд:

• набор должен быть непустой; то есть хотя бы одно блюдо должно быть подано, $$$k \ge 1$$$;
• все блюда в наборе должны быть приготовлены попарно различными способами;
• не более половины поданных блюд должны быть приготовлены с использованием одного и того же ингредиента в качестве основного; иными словами, для любого ингредиента число блюд с ним в основе должно не превосходить $$$\left\lfloor\frac{k}{2}\right\rfloor$$$.

Шефа интересует, сколько есть различных способов выбрать набор произвольного размера из множества $$$A$$$ возможных блюд, который удовлетворит критиков? Наборы считаются различными, если есть хотя бы одно блюдо, присутствующее в одном из них, но не в другом. Поскольку это число может быть большим, найдите остаток от его деления на $$$998\,244\,353$$$.

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