На прошлый новый год друзья подарили Мише клетчатое поле из 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 операций обмена соседних солдат.

У маленькой Даши сегодня день рождения — ей исполнилось целых 8 лет! По такому случаю каждый из n её родственников и друзей подарил ей ленточку с праздничным поздравлением, причём, как оказалось, все поздравления отличаются друг от друга. Даша собрала все ленточки вместе и решила выкинуть некоторые из них так, чтобы оставшийся набор стал стильным . Именинница считает набор стильным, если ни одно поздравление не является подстрокой другого. Напомним, что подстрокой строки s называется непрерывный отрезок букв строки s .

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

Разбойники с большой дороги Джон и Боб ограбили караван и в качестве добычи получили три золотых слитка. Решив поделить добычу по-братски, Джон и Боб взвесили слитки и выяснили, что они весят \(x_1\), \(x_2\) и \(x_3\) фунтов, соответственно.

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

Помогите Джону и Бобу выбрать, какой слиток распилить на две части, и на какие части его следует распилить, чтобы после этого можно было поделить добычу поровну.

Каждое утро Антон едет на работу на автобусе.

Маршрут автобуса включает в себя \(n\) остановок, пронумерованных от 1 до \(n\) в порядке следования. Автобус проезжает от каждой остановки до следующей за одну минуту, а его временем стоянки можно пренебречь. Антон садится на первой остановке и выходит на последней.

В автобусе есть m сидений, которые расположены в один ряд и пронумерованы от 1 до \(m\), ближайшее к входу сиденье имеет номер 1, а самое дальнее — номер \(m\). На каждом сиденье может сидеть один пассажир, а также возле каждого сиденья может стоять один пассажир.

Когда человек входит в автобус, он садится на ближайшее ко входу свободное сиденье. Если они все заняты, он ищет ближайшее ко входу сиденье, рядом с которым никто не стоит, и встаёт у сидящего там человека над душой. Если такого места нет, он выходит из автобуса.

Каждый пассажир остаётся на своём месте до прибытия на нужную ему остановку. Стоящий пассажир остаётся стоять, даже если какое-то сиденье освободилось.

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

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