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

Решения, выводящие правильный ответ при дополнительных ограничениях $$$N \leq 2000,$$$ будут набирать не менее 50 баллов.

Прораб Иван Иванович купил $$$N$$$ килограмм гравия для своей стройки. Гравий можно транспортировать только в мешках. На базе стройматериалов, где закуплен гравий, есть мешки для гравия любой вместимости от $$$a$$$ до $$$b$$$ килограмм (включительно). Мешок можно засыпать гравием только полностью. Иван Иванович хочет перевезти как можно большую часть купленного гравия в таких мешках на свой строительный объект. При этом он хочет обойтись как можно меньшим количеством мешков. Сколько мешков ему необходимо перевезти?

Начинающий шахматист Вася исследовал возможные движения шахматного коня по шахматной доске ($$$8\times 8$$$ клеток): его конь начал движение с некоторой клетки с номером строки $$$x$$$ и номером столбца $$$y$$$ и совершил $$$n$$$ ходов по правилам шахматного коня (шахматный конь ходит буквой «Г»: за один ход он совершает прыжок или на одну клетку по горизонтали и одновременно на две клетки по вертикали, или на две клетки по горизонтали и одновременно на одну клетку по вертикали, в обоих случаях прыжок по горизонтали и по вертикали может совершаться в любом направлении). Вася старательно записывал координаты каждой клетки, которую посещал конь после очередного хода. Но в какой-то момент он увлёкся и забыл записать ход, поэтому в его записях оказались координаты только $$$n-1$$$ клетки. Вася уверен, что все остальные клетки он записал корректно и теперь по своим записям хочет восстановить номер пропущенного хода и координаты клетки, в которой мог оказаться конь после этого хода.

Дана таблица неотрицательных целых чисел $$$N\times M$$$ ($$$N$$$ строк и $$$M$$$ столбцов) и размеры окна, накладываемого на эту таблицу: $$$n \times m$$$ ($$$n$$$ строк и $$$m$$$ столбцов, $$$1 \leq n \leq N,$$$ $$$1 \leq m \leq M$$$). Далее для всех возможных положений окна вычисляется XOR всех чисел, попавших в окно (определение операции приведено ниже). Затем вычисляется XOR всех полученных результатов для окон. Необходимо определить, какое число получится в результате.

Операция XOR (побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ) для двух целых чисел определяется следующим образом: числа представляются в двоичной системе счисления и вычисляется поразрядная сумма по модулю 2, в итоге получается двоичное представление результата операции. Например: $$$$$$ 5\,XOR\,3 = 101_2\,XOR\,011_2 = 110_2 = 6. $$$$$$ Операция XOR присутствует во многих языках программирования. Например, в языке Pascal для её вычисления используется оператор $$$xor,$$$ в языках C, C++, Python, Java оператор ^.

Нетрудно показать, что операция XOR ассоциативна и коммутативна, поэтому в условии не оговорено, в каком порядке проходятся все возможные положения окна и в каком порядке обходятся числа в окне при вычислении операции.

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

Миллионер Билл подал в мэрию прекрасного курортного города заявку на покупку участка на побережье. Администрация города согласилась выделить миллионеру участок, но выставила требование: в целях соблюдения принципов городского планирования участок обязательно должен быть прямоугольной формы и одна из его сторон должна быть параллельна гряде гор, идущих вдоль побережья. Побережье представляет собой последовательность прямоугольных полос ширины один метр, одна из метровых сторон которых упирается в гряду гор, представляющую собой прямую линию. Полосы касаются друг друга боковыми сторонами. Море находится с противоположной от гор стороны полос (см. рисунок). Помогите Биллу выбрать участок максимальной площади, удовлетворяющий требованиям мэрии.

Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Решение задачи оценивается независимо на каждом тесте. За каждый успешно пройденный тест, кроме тестов из условия, начисляется 2 балла. Прохождение тестов из условия является необходимым условием для оценивания задачи на остальных тестах. Остальные тесты оцениваются независимо друг от друга. Тесты разбиты на следующие группы тестов, соответствующие номеру подзадачи $$$t$$$ во входных данных задачи: