Алгоритмы

Последовательность Фибоначчи определяется так: \(f_0 = 0, f_1 = 1, ..., f_n = f_{n-1}+f_{n-2}\).

По данному числу n определите n-е число Фибоначчи fn.

Входные данные
Программа получает на вход натуральное число n.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	6	8

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K−1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A₁ рублей. Те, у кого совпали первые две цифры числа — получают A₂ рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A₃ рублей. И так далее. Угадавшие все число полностью получают Am рублей. При этом если игрок угадал t первых цифр, то он получает A_t рублей, но не получает призы за угадывание t−1, t−2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

Входные данные
В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1 ≤ N ≤ 100000), M (длина чисел 1 ≤ M ≤ 10) K (основание системы счисления 2 ≤ K ≤ 10). В следующей строке записаны M чисел A₁, A₂, ..., A_M, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1 ≤ A₁ ≤ A₂ ≤ ... ≤ A_M ≤ 100000). В каждой из следующих N строк записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

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

Примеры

№	Входные данные	Выходные данные
1	10 3 2 1 3 100 000 000 001 010 100 100 100 100 110 111	011 6
2	1 1 10 100 0	1 0

У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:

• + x — добавить в мультимножество A число x.
• - x — удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
• ? x — вам даётся число x, требуется вычислить максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.

Мультимножество — это множество, в котором разрешается несколько одинаковых элементов.

Входные данные:
В первой строке входных данных содержится число q (1 ≤ q ≤ 200000) — количество запросов, которые требуется обработать Василию.

Каждая из последующих q строк входных данных содержит один трёх символов «+», «-» или «?» и число x_i (1 ≤ x_i ≤ 10⁹). Гарантируется, что во входных данных встречается хотя бы один запрос «?».

Обратите внимание, что число 0 всегда будет присутствовать в мультимножестве.

Выходные данные:
На каждый запрос типа «?» выведите единственное целое число — максимальное значение побитового исключающего ИЛИ для числа x_i и какого-либо числа из мультимножества A.

Пример:
 

Входные данные	Выходные данные
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11	11 10 14 13

Эн идет в свой Грибной лес собирать грибы.

В Грибном лесу m ориентированных дорожек, соединяющих n деревьев. На каждой дорожке растут грибы. Когда Эн проходит по дорожке, он собирает все грибы на этой дорожке. Однако, в Грибном лесу такая плодородная почва, что грибы растут с фантастической скоростью. Новые грибы вырастают, как только Эн заканчивает собирать грибы на дорожке. А именно, после того, как Эн проходит по дорожке в i-й раз, вырастает на i грибов меньше, чем было до этого прохода. Таким образом, если на дорожке изначально было x грибов, то Эн соберет x грибов в первый проход, x - 1 гриб во второй, x - 1 - 2 гриба в третий и так далее. Однако, количество грибов не может стать меньше 0.
Например, пусть изначально на дорожке росло 9 грибов. Тогда количество грибов, которое соберет Эн, равно 9, 8, 6 и 3 для проходов с первого по четвертый. Начиная с пятого прохода и далее Эн ничего не сможет собрать с этой дорожки (но все еще может по ней ходить).

Эн решил начать от дерева s. Какое максимальное количество грибов он может собрать, передвигаясь только по описанным дорожкам?

Входные данные:
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — количество деревьев и количество ориентированных дорожек в Грибном лесу, соответственно.
Каждая из следующих m строк содержит три целых числа x, y и w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10⁸), описывающих дорожку, которая ведет от дерева x к дереву y с w грибами изначально. Возможны дорожки, которые ведут от дерева к нему же, а также несколько дорожек, соединяющих одну и ту же пару деревьев.
Последняя строка содержит одно целое число s (1 ≤ s ≤ n) — начальную позицию Эна.

Выходные данные:
Выведите одно целое число — максимальное число грибов, которое может собрать Эн на своем пути.

Примеры:
 

Входные данные	Выходные данные
2 2 1 2 4 2 1 4 1	16
3 3 1 2 4 2 3 3 1 3 8 1	8

Пояснения:
В первом примере Эн может три раза пройти по кругу и собрать 4 + 4 + 3 + 3 + 1 + 1 = 16 грибов. После этого не будет грибов, которые Эн может собрать.
Во втором примере Эн может пойти к дереву 3 и собрать 8 грибов на дорожке от дерева 1 до дерева 3.

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, которые пронумерованы числами от 1 до N, причем сам Мирко имеет номер 1. У всех работников, кроме Мирко, есть начальник. Начальник может иметь несколько подчиненных, но не более одного своего начальника.

Когда Мирко получает задание от инвесторов, он передает его своему подчиненному с наименьшим номером. Этот подчиненный также передает его своему подчиненному с наименьшим номером, и так далее, пока задание не перейдет несчастливому работнику без подчиненных, который должен его выполнить.
Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 монеты, и так далее. Потом тот, кто на самом деле сделал работу, осознает, насколько эта капиталистическая система несправедлива, и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации.

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

Входные данные:
Первая строка содержит одно натуральное число N (1 ≤ N ≤ 2·10⁵) — число сотрудников компании. Следующая строка содержит N-1 чисел a₂, a₃, ... a_n (1 ≤ a_i < i), a_i — номер начальника i-го сотрудника.

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

Примеры:
 

Входные Данные	Выходные данные
3 1 1	5 1 1
5 1 2 2 4	13 8 1 3 1

Пояснения:

Далее приведено описание ко второму примеру.

Мирко отдает первое задание работнику 2, который передает его работнику 3, который выполняет задание. Таким образом, работник 3 получает одну монету, работник 2 — две монеты, а работник 1, сам Мирко, — три монеты. После этого работник 3 увольняется.
Мирко отдает второе задание работнику 2, который передает его работнику 4, который тут же передает задание работнику 5, который выполняет задание. После этого работник 5 получает одну монету, работник 4 — две монеты, работник 2 — три монеты, а Мирко — четыре монеты. Работник 5 увольняется.
После выполнения третьего задания работник 4 получает одну монету, работник 2 — две монеты, а Мирко — три монеты, после чего работник 4 увольняется.
После выполнения четвертого задания работник 2 получает одну монету, а Мирко — две монеты, после чего второй работник увольняется.
Наконец, пятое задание выполняет сам Мирко, получая за это одну монету, после чего процесс прекращается.

Суммарно Мирко получил 13 монет, работник 2 — 8 монет, работник 4 — 3 монеты, а работники 3 и 5 — одну монету.

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p₁, p₂, …, p_n} будет лексикографически меньше перестановки {q₁, q₂, …, q_n}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого p_j = q_j при j < i и p_i < q_i.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется написать программу, позволяющую найти m-ую k-перестановку в этом порядке.

Входные данные
Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 10⁹). Вторая строка содержит n различных натуральных чисел, не превосходящих 10⁹. Все числа в строках разделены пробелом.

Выходные данные
В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 8 3 9	3 9 6 8
2	4 4 2 6 8 3 9	9 3 6 8
3	4 5 2 6 8 3 9	-1

Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено N точек, в которых может находиться клад. Все точки пронумерованы числами от 1 до N. Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером 1. Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером 1 никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.

Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.

Входные данные
В первой строке находится одно целое число N (1 ≤ N ≤ 15) — количество точек, отмеченных на карте. В последующих N строках находятся расстояния между точками. В (i+1)-й строке находятся N целых чисел d_i1,d_i2, d_iN — длины дорог от i-й точки до всех остальных. Гарантируется, что d_ij=d_ji, d_ii=0 и 0 <d_ij <100. В (N+2)-й строке находится одно целое число Q (1 < Q ≤ 1000) — количество вариантов вычеркивания точек для данной карты. В последующих Q строках содержится описание вариантов вычеркивания. Описание начинается с числа C (0 ≤ C < N) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие C чисел задают номера этих точек.

Выходные данные
Выведите Q строк. В каждой строке выведите одно целое число — длину минимального маршрута при соответствующем варианте вычеркивания точек.

Примеры

№	Входные данные	Выходные данные
1	3 0  45 10 45 0  30 10 30 0 2 0 1 3	40 45
2	5 0  14 20 17 14 14 0  15 19 18 20 15 0  15 16 17 19 15 0  14 14 18 16 14 0 2 3 5 4 3 0	14 58

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

Входные данные:
Первая строка содержит одну строку четной длины от 2 до 200, состоящую из строчных букв латинского алфавита.

Выходные данные:
В первой строке вывести минимальное количество замен букв.

Пример:
 

Входные данные	Выходные данные
baddaacc	1

Пояснение:
Можно заменить шестую букву на b, тогда процесс удаления будет выглядеть следующим образом: baddabcc -> baddab -> baab -> bb ->  .
 

У Макс в блокноте были записаны две строки s длины n и t длины m, состоящие из букв «a» и «b» латинского алфавита. Причем Макс знает, что строка t имеет вид «abab...», то есть на нечетных позициях строки стоит буква «a», а на четных — «b».

Вдруг утром Макс обнаружила, что кто-то испортил ее строку s. Некоторые буквы s были заменены на символ «?».

Назовем последовательность позиций i, i + 1, ..., i + m - 1 вхождением строки t в s, если 1 ≤ i ≤ n - m + 1 и t₁ = s_i, t₂ = s_i + 1, ..., t_m = s_{i + m - 1}.

Красота строки s оценивается как максимальное количество непересекающихся вхождений строки t в нее. Макс может заменить некоторые из символов «?» на «a» или «b» (символы на разных позициях можно заменять на разные буквы). Макс хочет произвести замены так, чтобы красота строки s была максимально возможной. Из всех таких вариантов она хочет заменить как можно меньше символов «?». Найдите, сколько замен она должна сделать.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵) — длину строки s.
Вторая строка входных данных содержит строку s длины n, состоящую только из букв «a» и «b» латинского алфавита, а также символов «?».
Третья строка содержит целое число m (1 ≤ m ≤ 10⁵) — длину строки t. Сама строка t содержит «a» на нечетных позициях, и «b» на четных.

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

Примеры:
 

Входные данные	Выходные данные
5 bb?a? 1	2
9 ab??ab??? 3	2

Пояснения:
В первом примере строка t имеет вид «a». Единственный оптимальный вариант — заменить все символы «?» на «a».
Во втором примере используя две замены можно получить строку «aba?aba??». Больше двух вхождений получить нельзя.

Вам дан массив из n целых чисел. Вам необходимо разделить его на k непустых подотрезков (последовательность подряд идущих элементов) так, чтобы:
1) Каждый элемент массива входил ровно в один подотрезок.
2) Если для каждого подотрезка выбрать минимальное в нем число, то сумма всех минимумов должна быть максимально возможной.

Сообщите сумму минимумов значений в подотрезках этого разбиения.

Входные данные:
В первой строке дается два натуральных числа - n (1 <= n <= 500) и k (1 <= k <= n).
Во второй строке дается n целых чисел - элементы массива a_i (1 <= a_i <= 10⁵).

Выходные данные:
Выведите одно число - ответ на задачу.

Пример:
 

Входные данные	Выходные данные
5 3 4 2 5 1 3	8

Пояснение:
Одно из подходящих разбиений: [4, 2], [5], [1, 3]. Сумма минимумов в каждом подотрезке равна 2 + 5 + 1 = 8.

Макс находится на начальной станции поезда, и сейчас в него хотят зайти n человек (включая саму Макс). Они уже выстроились в некотором порядке, и для каждого из них известен код города a_i, в который они направляются.

Начальник поезда выбирает некоторое количество непересекающихся отрезков исходной последовательности людей (отрезки не обязаны покрывать всю последовательность). Люди, находящиеся в одном и том же отрезке, будут находиться в одном и том же вагоне поезда. Отрезки выбираются так, что если в город X едет как минимум один человек, то все люди, которые направляются в город X должны будут находиться в одном вагоне. Это обозначает, что они не имеют права принадлежать разным отрезкам. Следует заметить, что все люди, которые едут в город X, либо едут в него и находятся в одном вагоне, либо вовсе не едут никуда.

Комфортность поездки в поезде с людьми на отрезке с l по r равна XOR-у различных кодов городов у людей на отрезке с l по r. Операция XOR также известна как исключающее побитовое ИЛИ.

Общая комфортность выбранных отрезков вычисляется как сумма комфортности каждого отдельного отрезка.

Помогите Макс узнать максимальную достижимую общую комфортность.

Входные данные:
Первая строка содержит натуральное число n - число людей (1 <= n <= 5000).
Вторая строка содержит n целых чисел a_i (0 <= a_i <= 5000) - код города, в который направляется i-й человек.

Выходные данные:
Выведите одно целое число - максимальную общую комфортность.

Примеры:
 

Входные данные	Выходные данные
6 4 4 2 5 2 3	14
9 5 1 3 1 5 2 4 2 5	9

Казума путешествует с тремя спутницами: Аквой, Мегумин и Даркнесс. Но за путешествия не платят, поэтому нашему отряду необходимо выполнять задания, порученные гильдией авантюристов.

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

Отношение каждой из спутниц к Казуме характеризуется целым числом. Изначально отношение каждой из них нейтрально и равно 0. В процессе выполнения задания отношение девушек, которых он взял на задание, к нему меняется в положительную или отрицательную сторону (а может и не меняться вовсе).

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

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

Входные данные:
В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения.
Следующие n строк содержат описание заданий — i-я строка содержит три числа a_i, m_i, d_i — величины, на которые изменятся отношения к Казуме Аквы, Мегумин или Даркнесс соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания. 
Все числа во входных данных целые и не превышают по абсолютному значению 10⁷.

Выходные данные:
В случае, если решения не существует, в первой строке выведите "Impossible".
В противном случае выведите отношение, которое будет у всех девушек по отношению к Казуме и при этом максимально возможное.

Примеры:
 

Входные данные	Выходные данные
3 1 0 0 0 1 0 0 0 1	1
7 0 8 9 5 9 -2 6 -8 -7 9 4 5 -4 -9 9 -4 5 2 -6 8 -7	5
2 1 0 0 1 1 0	Impossible

Дан массив A, состоящий из n целых положительных чисел, и число m. Выберите последовательность позиций B1, B2, ..., Bk (1 <= B₁ < B₂ < ... < B_k <= n) такую, чтобы значение  \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) было максимально (то есть, чтобы остаток от деления суммы элементов подпоследовательности на число m был максимально возможным). Выбранная последовательность может быть пустой.
Посчитайте максимальное возможно значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Входные данные
В первой строке даны два целых числа n и m (1 <= n <= 35, 1 <= m <= 10⁹). Во второй строке дано n целых чисел A1, A2, ..., An (1 <= A_i <= 10⁹)

Выходные данные
Выведите одно число - максимальное значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 

Примеры

№	Входные данные	Выходные данные
1	4 4 5 2 4 1	3
2	3 20 199 41 299	19

 

Пояснения

В первом примере можно выбрать B = {1, 2}. (A1 + A2) mod m = (5 + 2) % 4 = 3.
Во втором примере можно выбрать B = {3}.

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

Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n. 
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут. 
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете. 
                                                                                   
Уставший Петя пошел к себе домой, а утром Вася показал ему план, на котором бункеры были обозначены точками, а тоннели отрезками. 
Кроме того, Вася выбрал штаб-квартиру таким образом, что нарисованный им план был симметричен относительно прямой, проходящей через точку, которая соответствовала штаб-квартире.
 
Хотя Петя почти сразу показал Васе, что тот ошибся и не нарисовал половину бункеров, ему стало интересно, можно ли выбрать штаб-квартиру и нарисовать такой симметричный план.

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 10⁵) - количество бункеров. 
В следующих n - 1 строках находится по два целых числа u_i и v_i (1 <= u_i, v_i <= n, u_i ≠ v_i) - номера бункеров, которые соединяет i-ый тоннель. 
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:
 

Входные данные	Выходные данные
2 1 2	NO
3 1 2 2 3	YES

У Гекльберри Финна есть две строки s и t одинаковой длины n.
Гекльберри Финну нравится, когда у строк одинаковые префиксы (начала), поэтому он может поменять местами два символа в строке s, чтобы общий префикс строк s и t стал больше.
Однако этот трюк довольно утомительный, поэтому Гекльберри Финн либо совсем не будет его делать, либо сделает ровно один раз.

Помогите Гекльберри Финну определить наибольшую длину общего префикса строк s и t, которую он может получить.


Входные данные:
В первой строке дано натуральное число n (1 <= n <= 200000) - длина строк s и t
Во второй строке дана строка s, состоящая из строчных латинских букв.
В третьей строке дана строка t, состоящая из строчных латинских букв.

Выходные данные:
Выведите одно натуральное число - наибольшую длину общего префикса s и t, которую можно получить, применив операцию обмена двух символов в строке s не более одного раза.

Примеры:
 

Входные данные	Выходные данные
3 wai add	1
5 qdyid xreac	0

Во время покраски забора Том Сойер написал на нем слово s. Однако затем он решил, что слова-палиндромы смотрятся красивее.
Теперь он хочет дописать к имеющемуся слову s справа другое слово g так, чтобы получившееся слово sg было палиндромом. Однако в целях экономии краски длина g должна быть как можно меньше.
Помогите Тому Сойеру определить слово g.

Входные данные:
В первой строке дано слово s (1 <= |s| <= 200000), состоящее из строчных латинских букв.

Выходные данные:
Выведите минимально возможное по длине слово g, которое нужно дописать, чтобы слово sg на заборе стало палиндромом. Если дописывать ничего не надо, то выведите '-'.

Примеры:
 

Входные данные	Выходные данные
abc	ba
a	-

В связи с приближающимся завершением эпидемии коронавируса правительство города Энска приняло решение отправить на южные морские курорты отличников школ города - N отдыхающих.
В авиакомпаниях для перевозки имеются K типов самолётов с различным количеством пассажирских мест (P₁, P₂,...,P_k). Необходимо решить логистическую задачу: зарезервировать необходимое количество рейсов (R₁, R₂,...,R_k).
Суммарное количество посадочных мест не может быть меньше, чем количество пассажиров, а общее количество незанятых пассажирских мест (V) должно быть минимальным. Если будет обнаружено несколько вариантов, одинаковых по количеству незанятых мест, то следует выбрать вариант с меньшим общим количеством рейсов самолётов. Если и таких вариантов будет несколько, то нужно вывести любой из них.
Входные данные
в первой строке через пробел записаны 2 натуральных числа N и K, во второй - K натуральных чисел P₁ P₂ … P_k. N не превышает 10000, K не превышает 20, любое P_i меньше 500.
Выходные данные
в первой строке вывести число V, во второй через пробел вывести R₁ R₂ … R_k. Порядок количеств рейсов должен соответствовать исходному порядку типов самолётов.

Примеры

№	Входные данные	Выходные данные
1	1000 3 300 220 150	30 0 0 4 1
2	80 4 100 50 40 30	0 0 1 0 1 (вариант - 0 0 2 0)

Фермер Джон хочет сфотографировать своих пасущихся коров, чтобы повесить эту фотографию на стене. Пастбище представлено решёткой из N * N ячеек (как шахматная доска размером N×N) (2≤N≤1000). ФД хочет, чтобы коровы были распределены по пастбищу с выполнением следующих правил:
Никакие две коровы не могут находится в одной и той же ячейке.
Каждая подрешётка размером 2×2 (всего таких подрешёток (N−1)×(N−1)) должна содержать ровно 2 коровы
Например, такое размещение соотвествует правилам:

CCC
...
CCC
А такое размещение - нет

C.C
.C.
C..
поскольку 2×2 регион в правом нижем углу содержит только одну корову.
Других ограничений нет. Вы можете считать, что у ФД есть бесконечное количество коров.

Некоторые ячейки более предпочтительный для ФД, нежели другие. В частности, ФД считает. что если корова размещена в ячейке (i,j), красота фотографии увеличивается на a_ij (0≤a_ij≤1000) единиц.

Определите максимально возможную красоту корректного размещения коров.

Входные данные
Первая строка содержит число N. Каждая из следующих N строк содержит по N целых чисел. j-ое число в i-ой строке сверху есть значение a_ij.
Выходные данные
Выведите одно целое число - максимально возможную красоту результирующего фото.

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	4 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3 3	22	В этом примере максимальная красота может быть достигнута следующим размещением: CC.. ..CC CC.. ..CC Красота этого размещения 3+3+3+1+3+3+3+3=22.

Малоизвестен тот факт, что у коров свой алфавит "cowphabet". Он состоит из тех же 26 букв от 'a' до 'z', но в другом порядке.
Чтобы скоротать время, Беси бормочет cowphabet опять и опять. Фермеру Джону интересно, сколько раз она его пробормотала.

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

Входные данные
Первая строка ввода содержит 26 маленьких латинских букв от 'a' до 'z' в порядке их появления в cowphabet. Следующая строка содержит строку из маленьких латинских букв, которые услышал ФД. Эта строка имеет длину от 1 до 1000.
Выходные данные
Выведите минимальное количество раз, которое Беси пробормотала алфавит.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	abcdefghijklmnopqrstuvwxyz mood	3	В этом примере cowphabet упорядочен как нормальный алфавит. Бесси пробормотала cowphabet как минимум 3 раза. Ниже показано, как Беси бормотала, и большими буквами - какие буквы услышал ФД. abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 100) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.