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

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

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

Командам предстоит написать n тренировок в течение n последовательных дней. Во время каждой тренировки на каждую команду, пришедшую в этот день, Серёжа заказывает по пицце в своей любимой пиццерии. Серёжа уже знает, что на i -ю тренировку придёт ровно a _i команд.

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

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

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

Маленький Влад обожает играть в популярную игру Bota-2 на своем компьютере. На днях разработчики сообщили о выходе её продолжения под названием Bota-3. Разумеется, Влад тут же её приобрёл, но оказалось, что компьютер Влада слишком старый для этой игры, поэтому он отправился в магазин за обновлением для него.

В магазине Влад увидел n видеокарт, i -я из которых имеет свою мощность a _i , выражаемую целым положительным числом. Для того, чтобы игра точно заработала, Влад решил купить не одну, а несколько видеокарт и объединить их мощности по новейшей технологии. Для использования этой технологии одна из видеокарт выбирается в качестве ведущей, а все остальные видеокарты подключаются к ней в качестве вторичных. Для корректной работы этой конструкции необходимо, чтобы мощность каждой видеокарты была кратна мощности ведущей видеокарты. Для обеспечения совместимости мощность каждой вторичной видеокарты может быть понижена до любого меньшего целого положительного значения. При этом мощность опорной видеокарты должна оставаться оригинальной, то есть не может быть уменьшена.

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