Гарри Поттер и Тот-Кого-Нельзя-Называть снова сошлись в смертельном поединке. На этот раз они стоят в противоположных концах коридора длины l метров и одновременно пускают в противника свои смертельные заклинания. Известно, что магический импульс заклинания Гарри распространялся со скоростью p метров в секунду, а магический импульс заклинания Сами-Знаете-Кого — со скоростью q метров в секунду.

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

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

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

Так как дороги всегда обходятся недёшево, правительства государств новообразованного союза попросили вас помочь им оценить затраты. Для этого вам была выдана карта, которая представляет собой клетчатый прямоугольник из n строк по m клеток в каждой. Любая клетка карты либо принадлежит одному из трёх государств, либо является областью, на которой можно построить дорогу, либо является областью, на которой дорогу построить нельзя. Проходимыми являются все клетки, принадлежащие государствам, а также все клетки, в которых построены дороги. Из любой проходимой клетки можно перемещаться вверх, вниз, вправо и влево, если соответствующая такому перемещению клетка существует и является проходимой.

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

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

На планете Бублик идёт война. Каждый из городов планеты принадлежит одному из нескольких враждующих государств. На планете есть n городов, расположенных вокруг дырки от Бублика и пронумерованных числами от 1 до n в порядке их обхода по кругу. Расстояние между любыми двумя соседними по кругу городами (в том числе между городом номер n и городом номер 1 ) одно и то же, а именно 42 бубликанских километра.

Когда на какой-то город происходит нападение, из него в противоположных направлениях выбегают два гонца. Двигаясь с одинаковой постоянной скоростью, они пробегают полный круг, предупреждая о нападении все города этого государства на своём пути. Чем больше максимальное время, которое пройдёт между нападением на какой-то город государства и моментом, когда все города этого государства будут оповещены о нападении, тем более уязвимым является данное государство. Вы решили выбрать наиболее уязвимое государство и предупредить его об опасности.

Вам дана политическая карта планеты Бублик. Требуется найти два города, принадлежащих одному государству, расстояние между которыми максимально.

На прошлый новый год друзья подарили Мише клетчатое поле из n строк и m столбцов, в каждой клетке которого записано некоторое целое число c _{i , j} , где i определяет номер строки, а j — номер столбца. Строки пронумерованы сверху вниз, а столбцы — слева направо. Строки и столбцы занумерованы целыми числами, начиная с единицы.

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

Задача была бы практически невыполнима, если бы Миша не прочитал прилагавшуюся к клетчатому полю инструкцию. В ней было сказано, что на самом деле число c _{i , j} равняется a _i & b _j , где a и b — две последовательности чисел, любезно указанных в инструкции, а операция & означает побитовое умножение или побитовое «И» (определение операции смотрите в разделе «Замечание»).

В сверхсекретную военную часть под командованием полковника Зуева скоро приедет комиссия из министерства обороны. Согласно уставу, в каждой сверхсекретной военной части должна быть сверхсекретная рота, которая должна заниматься... а чем именно — не скажем, на то она и сверхсекретная. Проблема заключается в том, что в части Зуева такой роты почему-то нет.

Полковник решил разобраться с этой проблемой незамедлительно и приказал построить на плацу в одну шеренгу всех n солдат вверенной ему части. Известно, что болтливость i -го слева солдата равна q _i . Зуев хочет, чтобы сверхсекретная рота состояла из k первых солдат шеренги, а их суммарная болтливость была как можно меньше (чтобы рота оставалсь сверхсекретной). Для этого он собирается не более s раз поменять местами двух соседних солдат. Заметим, что любой солдат может участовать в таком обмене позициями сколько угодно раз. Задача оказалась нетривиальной, и полковник Зуев обратился к вам за помощью. Определите, какую минимальную суммарную болтливость первых k солдат шеренги можно достичь, если провести не более s операций обмена соседних солдат.