Алгоритмы

Задано четыре числа: \(a\), \(b\), \(c\) и \(d\). Требуется разбить их на две пары, чтобы сумма произведений в этих парах была максимальна.

Например, если заданы числа 2, 3, 4 и 5, то оптимально разбить их на пары \((2, 3)\) и \((4, 5)\), в этом случае искомая сумма равна \(2 \times 3 + 4 \times 5 = 26\).

Формат входных данных
На вход подаются четыре числа: \(a\), \(b\), \(c\) и \(d\). Все числа по модулю не превышают 1000.

Формат выходных данных
Выведите искомую максимальную сумму.

У Саши есть блокнот, состоящий из \(n\) листочков, пронумерованных от 1 до \(n\). На \(i\)-м листочке написано целое число \(a_i\).

Аня собирается разорвать блокнот на \(k\) частей, для этого она выбирает \(k-1\) число \(1 \le r_1 < r_2 < \ldots < r_{k-1} < n\) и разрывает блокнот так, что листки с 1 по \(r_1\)-й оказываются в первой части, листки с \((r_1+1)\)-го по \(r_2\)-й оказываются во второй части, и т.д., последняя \(k\)-я часть содержит листки с \((r_{k-1}+1)\)-го по \(n\)-й.

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

Формат входных данных
Первая строка ввода содержит два числа: \(n\) и \(k\) (\(2 \le k \le n \le 300\)). Вторая строка содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

Формат выходных данных
На первой строке выведите максимальное значение суммы, которое удастся достичь Ане. На второй строке выведите значения \(r_1, r_2, \ldots, r_{k-1}\), которые ей необходимо выбрать. Если вариантов разорвать блокнот, чтобы максимизировать искомую сумму несколько, выведите любой из них.

Примечание
В приведенном примере Аня разорвала блокнот на части \([1, 10, 2]\), \([8]\), \([9]\), \([3, 5, 4]\) и \([7, 6]\). Искомая сумма равна \(1 + 8 + 9 + 3 + 6 = 27\).

На уроке физкультуры тренер Андрей Сергеевич выстраивает учеников в одну шеренгу. В шеренге сначала идут мальчики, а потом девочки. При этом мальчики в шеренге стоят по убыванию роста, аналогично девочки тоже стоят по убыванию роста. Таким образом, следом за самым низким мальчиком стоит самая высокая девочка.

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

Формат входных данных
Первая строка содержит целое число \(n\) — число учеников в классе (\(2 \le n \le 50\)). Следующие \(n\) строк содержат по два целых числа каждая: \(a_i\) и \(h_i\) — пол и рост в сантиметрах \(i\)-го ученика (\(a_i\) равно 0 или 1, \(100 \le h_i \le 200\)). Значение \(a_i = 0\) означает, что \(i\)-й ученик — мальчик, а значение \(a_i = 1\) означает, что \(i\)-й ученик — девочка.

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

Маша и Петя решили выяснить, чья комната больше. Машина и Петина комнаты имеют форму прямоугольников, причем Машина комната имеет размеры \(a\) на \(b\) метров, а Петина — \(c\) на \(d\) метров.

Напишите программу, которая определит, чья комната больше: Машина или Петина.

Формат входных данных
На ввод подается четыре натуральных числа, разделенных пробелами: \(a\), \(b\), \(c\) и \(d\) (\(1 \le a, b, c, d \le 1000\)).

Формат выходных данных
Если Машина комната больше, выведите латинскую букву <<M>>. Если Петина комната больше, выведите латинскую букву <<P>>. Если комнаты ребят имеют одинаковую площадь, выведите латинскую букву <<E>>.

В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.

Каждый день эксперимента устроен следующим образом. Рано утром профессор достает из контейнера все свои бактерии и помещает их в инкубатор, где бактерии начинают делиться. Вместо каждой бактерии образуется \(b\) новых бактерий.

После извлечения бактерий из инкубатора \(c\) из них используются для проведения различных опытов и затем уничтожаются. Если после извлечения из инкубатора имеется менее \(c\) бактерий, для проведения опытов используются все имеющиеся бактерии, и эксперимент заканчивается.

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

Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.

Формат входных данных
В единственной строке входного файла содержится пять целых чисел \(a\), \(b\), \(c\), \(d\) и \(k\) (\(1 \le a, b \le 1000\), \(0 \le c \le 1000\), \(1 \le d \le 1000\), \(a \le d\), \(1 \le k \le 10^{18}\)).

Формат выходных данных
Выведите одно число — количество бактерий у Хаоса к концу \(k\)-го дня. Если эксперимент завершится в \(k\)-й день или ранее, выведите число 0.

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

Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в \(K\) реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё \(N - 1\) реальностей. Для удобства они были занумерованы числами от \(1\) до \(N\), при этом его собственная реальность имеет номер \(1\), а посетить ему необходимо реальности с номерами \(2, 3, \ldots, K + 1\).

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени \(0\)). Исследование показало, что реальность с номером \(i\) ответвилась от реальности с номером \(P_i\) в момент времени \(T_i\). Из каждой реальности с номером \(i\) архимаг может переместиться

• в любую ответвившуюся от неё, то есть в любую \(j\), такую что \(P_j = i\);

• в \(P_i\), если \(i\) — не Начальная реальность.

Другими словами, возможны лишь переходы вида \(i \leftrightarrows P_i\). На каждый такой переход в любую сторону архимаг затрачивает \(T_i-T_{P_i} > 0\) условных единиц энергии.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером \(1\), посетить все реальности с номерами от \(2\) до \(K + 1\) (в любом порядке) и затем вновь вернуться в \(1\). Любую реальность при этом разрешается посещать сколько угодно раз.
Формат входных данных

Сначала вводятся два целых числа \(N\) и \(K\) (\(0 \leqslant K < N \leqslant 100\,000\)): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт \(N\) пар целых чисел, \(i\)-я пара — это \(P_i\) и \(T_i\) (\(1 \leqslant P_i \leqslant N\), \(0 \leqslant T_i \leqslant 10^6\); для Начальной реальности \(P_i=T_i=0\)).

Гарантируется, что ответвившаяся реальность появилась строго позже породившей (\(T_i > T_{P_i})\), и что маг может при желании добраться до любой из \(N\) реальностей.

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

Вася идет из школы домой вдоль проспекта, по которому ходят трамваи. Мама считает, что ему после школы полезно дышать свежим воздухом, поэтому настаивает, чтобы не менее \(K\) метров он прошел пешком. Вася при этом хочет попасть домой как можно быстрее (обязательно выполнив требование мамы).

Вдоль проспекта расположено \(N\) трамвайных остановок, которые находятся в точках \(a_1, a_2, \ldots, a_N\) (все координаты задаются в метрах). Школа находится около 1-й остановки, а дом — около остановки номер \(N\). Мальчик идет пешком со скоростью \(v\) метров в минуту. Трамвай едет со скоростью \(w\) метров в минуту (временем стоянки трамвая на остановках пренебрежем). В нулевой момент времени и далее с интервалом \(T\) минут от первой остановки в сторону Васиного дома отправляются трамваи. Вася выходит из школы также в момент времени 0. Сесть в трамвай и выйти из него можно только на остановке. При этом, если Вася приходит на остановку раньше трамвая, на который хочет сесть, то ему придется подождать, пока тот не подъедет. Вася идет пешком и едет на трамвае только в направлении от школы к дому.

Напишите программу, которая определит, когда Вася сможет оказаться дома.

Формат входных данных

Сначала вводится число \(N\) — количество остановок (\(1 \leqslant N \leqslant 2000\)). Далее заданы координаты остановок \(a_1, a_2, \dots, a_N\) (\(0 \leqslant a_1 < a_2 < \ldots < a_N \leqslant 10^9\)). Далее вводится интервал движения трамваев \(T\) (\(1 \leqslant T \leqslant 2000\)). Затем расстояние, не меньше которого Вася должен пройти пешком \(K\) (\(0 \leqslant K \leqslant 2000\)). Затем заданы скорости Васи \(v\) и трамвая \(w\) (\(1 \leqslant v \leqslant w \leqslant 10\,000\)). Все вводимые числа целые. \(K\) не превышает длины пути от школы до дома.

Формат выходных данных
В первую строку выведите не менее чем с пятью знаками после десятичной точки одно число — минимальное время, когда Вася сможет оказаться дома, пройдя пешком не менее \(K\) метров. Далее нужно вывести информацию о пути Васи. Занумеруем промежутки между соседними остановками числами от 1 до \(N-1\) (то есть промежуток между первой и второй остановками имеет номер 1, между второй и третьей — 2 и так далее). Следующая строка должна содержать количество промежутков, пройденных Васей пешком. Далее выведите номера этих промежутков в возрастающем порядке.

В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.

Игра идёт на доске с \(N\) строками и \(M\) столбцами (\(1 \le N \le 100\), \(1 \le M \le 100\)) по следующим правилам. В нижней строке, имеющей номер 1, стоит \(P\) белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, цель — достичь хотя бы одной пешкой самой верхней строки, имеющей номер \(N\) (Глеб слышал, что в этой ситуации из пешки можно сделать ферзя, а с такой силой он безусловно сможет побить все остальные чёрные фигуры).

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

Формат входных данных
Сначала вводятся четыре целых числа \(N\), \(M\), \(P\), \(K\) (\(1 \le N \le 100\), \(1 \le M \le 100\), \(0 \le P \le M\), \(1 \le K \le (N - 1)M\). Далее записано \(P\) различных чисел — номера столбцов \(p_j\) (\(1 \le p_j \le M\)), в которых стоят белые пешки. Далее идут \(K\) различных пар целых чисел — номера строк и столбцов чёрных фигур \(r_i\), \(c_i\) (\(2 \le r_i \le N\), \(1 \le c_i \le M\)).

Формат выходных данных
Если хотя бы одна пешка сможет достичь последнего ряда, выведите YES, в противном случае выведите NO.

Маленький Миша летом гостит у бабушки в деревне. Каждый день он съедает по одному фрукту и отмечает это в своем блокноте. Миша еще слишком мал и умеет рисовать только палочки (I) и галочки (V).  Каждый день, после того как он съел свой фрукт, он в блокнот рисует карандашом одну палочку (I) . Раз в пять дней он стирает четыре предыдущие палочки и рисует галочку (V).
Вас просят определить, какая запись получится у Миши на n-й день пребывания в деревне у бабушки.
 

Формат входных данных
На ввод подается одно число \(n\) (\(1 \le n \le 10\,000\)).

Формат выходных данных
Выведите запись, которая получится в блокноте у Миши на \(n\)-й день.

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

Изначально вам дан пустой стек и пустой массив. Кодом массива \(a\) назовем последовательность действий вида

• \(\mathtt{push}(x)\) — положить число \(x\) на вершину стека;

• \(\mathtt{pop}\) — снять число с вершины стека;

• \(\mathtt{print}\) — выписать в конец массива все элементы стека по порядку от нижнего к верхнему,

приводящую к тому, что в изначально пустой массив оказываются выписаны все элементы \(a\) по порядку. При выполнении третьей операции стек не очищается.

Например, при выполнении последовательности действий \(\mathtt{push}(1)\), \(\mathtt{push}(2)\), \(\mathtt{print}\), \(\mathtt{print}\), \(\mathtt{pop}\) и \(\mathtt{print}\) в массив оказываются выписаны числа \([1, 2, 1, 2, 1]\), а на стеке остается лежать только число \(1\). То есть такая последовательность является кодом массива \([1, 2, 1, 2, 1]\) длины \(6\).

Вам дан массив \(a\) и \(q\) запросов: какой у отрезка массива \(a\) с \(l_i\)-го по \(r_i\)-й элемент включительно минимальный по количеству действий со стеком код?

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

Формат входных данных
В первой строке ввода даны четыре целых числа \(n\) и \(q\) — длина массива \(a\), про отрезки которого спрашивается в запросах, количество запросов, а также максимальный балл за тест и параметр \(\gamma\), указанный в системе оценивания, которые ваше решение может игнорировать \((1 \le n \le 2000\); \(1 \le q \le 10^4\)).

Во второй строке перечислены \(n\) целых чисел \(a_i\) — элементы массива \(a\) (\(1 \le a_i \le 10^9\)).

В \(i\)-й из следующих \(q\) строк даны два целых числа \(l_i\) и \(r_i\) — границы отрезка из \(i\)-го запроса (\(1 \le l_i \le r_i \le n\)).

Формат выходных данных
Для каждого запроса выведите в отдельной строке целое число \(k\) от \(1\) до \(n + 1\) — количество действий в вашем коде соответствующего отрезка массива, после чего в следующей строке выведите через пробел \(k\) целых чисел, описывающих эти действия в порядке их выполнения:

• для действия \(\mathtt{push}(x)\) выведите число \(x\) от \(1\) до \(10^9\);

• для действия \(\mathtt{pop}\) выведите число \(-1\);

• для действия \(\mathtt{print}\) выведите число \(0\).

Если в результате выполнения выведенных действий происходит попытка снять число с вершины пустого стека или в конце не получается массив, равный заданному отрезку массива \(a\), ваше решение получает вердикт Wrong Answer. Также вы получите вердикт Wrong Answer, если в вашем коде будет больше \(n + 1\) действия.

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

Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито \(n\) сортов, \(i\)-й сорт характеризуется уровнем крепости \(p_i\) и высотой слоя, который он занимает в кружке, \(h_i\). При этом если \(i < j\), то слой кофе \(i\)-го сорта находится ниже кофе \(j\)-го сорта. Также известно, что высота кружки равна \(\sum\limits_{i=1}^n h_i\), то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.

Для разнообразия иногда хочется получить из такого <<коктейля>> напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как \[P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}\]

Чтобы как-то изменять \(P\), можно

1. выбрать трубочку произвольной высоты \(h\);

2. один или более раз выполнить следующее: погрузить ее в напиток на любую глубину от \(0\) до \(h\) включительно относительно верхнего края кружки (не относительно текущего уровня жидкости) и отпить произвольное (не обязательно целое) количество кофе с того уровня, на который попал нижний конец трубочки.

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

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

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(q\) — количество слоев кофе в кружке и количество запросов (\(1 \le n, q \le 2 \cdot 10^5\)).

Следующие \(n\) строк содержат по два целых числа \(p_i\) и \(h_i\) — уровень крепости и высоту \(i\)-го снизу кружки слоя кофе (\(1 \le p_i, h_i \le 10^9\)). Гарантируется, что сумма \(p_i \cdot h_i\) по всем \(i\) не превосходит \(10^{18}\).

В \(i\)-й из следующих \(q\) строк дано единственное целое число \(t_i\), определяющее \(i\)-й запрос (\(1 \le t_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых содержится единственное целое число от \(0\) до \(n\) — ответ \(i\)-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число \(-1\).

Замечание
Для примера из условия:

1. В первом запросе, чтобы получить напиток крепости \(1\), достаточно выпить верхние два слоя кофе.

2. Во втором запросе достаточно выпить часть кофе со второго сверху слоя.

3. В третьем запросе понадобится выпить первый и третий слой кофе.

4. В четвертом запросе невозможно добиться уровня крепости \(4\).

Если вас интересует математика, то эта задача для вас.

Будем называть целое число \(n\) \(k\)-степенным, если его можно разложить в сумму различных степеней числа \(k\), то есть если \(n\) представимо в виде \(n = k^{a_1} + k^{a_2} + \ldots + k^{a_d}\), где все \(a_i\) целые и \(a_i \ne a_j\) для всех \(i \ne j\).

Ответьте на множество запросов: какое минимальное целое число, большее либо равное \(n_i\), является \(k_i\)-степенным?

Формат входных данных
Первая строка ввода содержит целое число \(q\) — количество запросов, на которые вам предстоит ответить (\(1 \le q \le 10^5\)).

Каждая из следующих \(q\) строк содержит два целых числа \(n_i\) и \(k_i\), описывающие \(i\)-й запрос (\(1 \le n_i \le 10^9\); \(2 \le k_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых выведите минимальное \(k_i\)-хорошее число, большее либо равное \(n_i\).

Финальный турнир Флатландской Хоккейной Лиги (ФХЛ) играется между двумя командами-лидерами сезона. Команды играют матчи между собой до тех пор, пока одна из команд не выиграет ровно \(n\) матчей. Эта команда становится чемпионом ФХЛ. Каждый матч в финальном турнире заканчивается победой одной из команд, ничьих не бывает. Видеозаписи матчей публикуются на официальном сайте ФХЛ, так что все фанаты, которые пропустили матчи, могут посмотреть их в записи.

В этом году в финал вышли команды <<Капибары>> и <<Бурундучки>>. Петя и Вася очень любят хоккей, но во время турнира они были на сборах по информатике. Теперь они решили просмотреть все матчи финального турнира в записи, скачав их с официального сайта. Зайдя на сайт, они обнаружили, что в этом году финальный турнир ФХЛ состоял из \(k\) матчей. Скачав все видеозаписи, ребята начали их смотреть, но неожиданно поняли, что могут предсказать итог турнира, не досмотрев все матчи. Более того, они заметили, что про некоторые матчи они понимают, кто их выиграет, даже не начав смотреть запись.

Например, пусть \(n = 3\) и \(k = 4\). Петя и Вася сразу могут сделать вывод, что турнир закончится со счетом по матчам \(3:1\) или \(1:3\), ведь всего будет сыграно 4 игры. Пусть первый матч закончился победой команды <<Капибары>>, счет стал \(1:0\), второй матч также закончился победой команды <<Капибары>>, счет стал \(2:0\). Теперь ребята точно знают, что победителем турнира станет команда <<Капибары>>, ведь если бы турнир выиграла команда <<Бурундучки>>, то финальный счет был бы \(2:3\) и всего было бы сыграно 5 игр. Более того, команда <<Бурундучки>> гарантированно выиграет третий матч, иначе окончательный счет был бы \(3:0\), а команда <<Капибары>> "— четвертый матч.

По заданным \(n\), \(k\) и результатам игр определите, после какой игры Петя и Вася поймут, какая команда станет победителем турнира, а также про каждый матч определите, знают ли ребята победителя этого матча до того, как посмотрят его.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 100\), \(n \le k \le 2n-1\)). Вторая строка ввода содержит \(k\) целых чисел: \(i\)-е из них равно 1, если \(i\)-й матч выиграла команда <<Капибары>>, либо 2, если \(i\)-й матч выиграла команда <<Бурундучки>>.

Гарантируется, что по итогам турнира одна из команд выиграла ровно \(n\) матчей, причем ни одна из команд не выигрывает \(n\) матчей до того, как будут сыграны все \(k\) матчей, описанных во входных данных.

Формат выходных данных
Выведите две строки. Первая строка должна содержать одно число \(z\) (\(1 \le z \le k\)) "— номер матча, после которого ребята могут однозначно определить победителя турнира.

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

У Васи есть массив, состоящий из \(n\) чисел \(a_1, a_2, \ldots, a_n\). Для каждой позиции \(i\) и для каждого подотрезка массива \([l, r]\), который содержит позицию \(i\) (то есть, \(1 \le l \le i \le r \le n\)), Вася вычисляет значение \(c_{i, l, r}\) следующим образом. Вася выписывает на листочек числа из массива с позиции \(l\) до позицию \(r\), всего \(len=r-l+1\) чисел (среди которых обязательно есть \(a_i\)), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции \(j\) в полученном отсортированном массиве стоит число \(a_i\). Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции \(mid = \lceil (len+1) / 2 \rceil\) (\(len / 2 + 1\) в случае четного \(len\) и \((len+1)/2\) в случае нечетного \(len\)). Полученное расстояние \(|j - mid|\) и есть искомая величина \(c_{i,l,r}\).

Например, если у Васи был массив \(a=\{5,1,3,2,1,7\}\), а \(i=2\), \(l=2\), \(r=5\), то Вася выпишет на листочек числа \(\{1,3,2,1\}\), отсортирует их и получит массив \(\{1,1,2,3\}\), длина которого равна 4. Середина этого массива находится на позиции \(4/2+1=3\), а искомое число \(a_i=1\) стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение \(c_{2,2,5}\).

Для каждой позиции \(i\) Вася вычисляет величину \(b_i\), которая равна максимуму среди значений \(c_{i,l,r}\) среди всех подотрезков, содержащих позицию \(i\).

Как вы видите, определение числа \(b_i\) достаточно сложное. Помогите Васе вычислить значения \(b_i\) для всех позиций массива.

Формат входных данных
В первой строке входных данных находится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — размер массива Васи.

Во второй строке находится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — элементы массива.

Формат выходных данных
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно \(b_i\).

Разберем подробнее первый пример.

1. Для первой позиции Вася рассмотрит все подотрезки, содержащие эту позицию, в частности, подотрезок \([1,5]\), где \(l=1\) и \(r=5\). Для вычисления \(c_{i,l,r}=c_{1,1,5}\) Вася выпишет числа \(\{5, 4, 3, 2, 1\}\) и после сортировки получит \(\{1, 2, 3, 4, 5\}\). Середина этого массива находится на позиции 3, а искомое число \(a_1=5\) — на позиции 5. Таким образом, \(c_{1,1,5}=2\). Нетрудно заметить, что это число — максимальное среди всех подотрезков, содержащих позицию 1, а значит, \(b_1=2\).

2. \(b_2=c_{2,2,4}\).

3. \(b_3=c_{3,3,5}\).

4. \(b_4=c_{4,1,4}\). Действительно, если выписать числа на подотрезке \([1,4]\), то получится массив \(\{5,4,3,2\}\), который после сортировки превратится в \(\{2,3,4,5\}\). Середина этого массива находится на позиции \(3\), а искомый элемент \(a_4=2\) — на позиции 1. Таким образом, \(c_{4,1,4}=2\).

5. \(b_5=c_{5,1,5}\).

Пандемия охватила все страны мира, и Берляндия не стала исключением. Даже на Всеберляндской олимпиаде по информатике были введены противовирусные меры.

Всего в олимпиаде участвуют \(n\) человек, и, чтобы соблюсти все предписания руководства, жюри олимпиады решило приглашать участников на тур по одному с интервалом \(x\) минут. Таким образом первый участник начнёт тур в момент времени \(0\), второй участник начнёт тур в момент времени \(x\), третий — в момент времени \(2 \cdot x\) и так далее.

Несмотря на разное время начала, длительность тура для каждого участника составляет ровно \(t\) минут. Из-за этого некоторые участники заканчивают писать тур раньше остальных. Когда участник заканчивает писать тур, величина недовольства организацией олимпиады для этого участника равна числу других участников, которые в текущий момент времени еще пишут или только начинают писать тур, но еще не закончили его.

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

Формат входных данных
В первой строке вводится единственное целое число \(n\) (\(1 \le n \le 2 \cdot 10^9\)) — число участников олимпиады.

Во второй строке вводится единственное целое число \(x\) (\(1 \le x \le 2 \cdot 10^9\)) — интервал в минутах между временами начала тура для участников.

В третей строке вводится единственное целое число \(t\) (\(1 \le t \le 2 \cdot 10^9\)) — длительность тура.

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

В первом примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(5\). К этому времени второй и третий участники уже начнут писать тур, поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт писать в момент времени \(2\) и закончит в момент времени \(7\). К этому моменту третий и четвёртый участники уже начнут писать тур, поэтому недовольство второго будет равно \(2\).

Третий участник начнёт писать тур в момент времени \(4\) и закончит в момент времени \(9\). К этому времени четвёртый участник уже начнёт писать тур, поэтому недовольство третьего будет равно \(1\).

Четвёртый участник начнёт писать тур в момент времени \(6\) и закончит в момент времени \(11\). В момент времени \(9\) уже никто не будет писать тур, поэтому недовольство четвёртого будет равно \(0\).

Таким образом, суммарное недовольство всех участников будет равно \(2+2+1+0=5\).

Во втором примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(2\). К этому моменту второй участник уже будет писать тур, а третий участник как раз начнёт в момент времени \(2\). Поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт в момент времени \(1\) и закончит в момент времени \(3\). К этому моменту только третий участник будет всё ещё писать тур.

Таким образом, суммарное недовольство всех участников будет равно \(2+1=3\).

Перестановкой размера \(n\) называется массив \(\langle a_1, a_2, \ldots, a_n \rangle\) различных чисел от \(1\) до \(n\). Каждое число в перестановке встречается ровно один раз.

Сеня называет красотой перестановки \(\langle a_1, a_2, \ldots, a_n \rangle\) число \((a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n)\). Он хочет посчитать количество перестановок, красота которых делится на \(k\).

Даны числа \(n\) и \(k\), найдите количество перестановок размера \(n\), красота которых делится на \(k\).

Например, для \(n = 3\) существует \(6\) перестановок. Рассмотрим все эти перестановки и их красоту.

Формат входных данных
Входные данные содержат два целых числа: \(n\) и \(k\) (\(1 \le n \le 10\), \(2 \le k \le 1000\)).

Формат выходных данных
Выведите одно целое число: количество перестановок размера \(n\), красота которых делится на \(k\).

Далекая страна содержит \(n\) городов, соединенных \(n - 1\) дорогами, при этом из любого города можно добраться до любого другого по дорогам страны.

Известно, что каждый город относится ровно к одной провинции. Город \(v\) относится к провинции \(t_v\). Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер \(1\).

Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе \(v\) он равен \(c_v\).

Вам приходят запросы двух типов:

1. Изменить провинцию, к которой относится город \(v\), на \(t_{new}\)

2. В \(k\) городах с номерами \(a_1, a_2, \ldots, a_k\) появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции \(t\), после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером \(v\), то они получат \(c_v \cdot num_v\), где \(c_v\) — коэффициент города \(v\), а \(num_v\) это количество караванов, проходящих через этот город.

Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Формат входных данных
В первой строке даны два целых числа \(n\) и \(q\) (\(2 \le n \le 200\,000, 1 \le q \le 200\,000\)) — количество городов и количество запросов.

Во второй строке дано \(n - 1\) целое число \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i < i\)), где число \(p_i\) означает, что существует дорога между городами \(i\) и \(p_i\).

В третьей строке дано \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le n\)) — номера провинций у городов.

В четвертой строке дано \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^9\)) — коэффициенты успешности грабежа.

Далее идет \(q\) строк описаний запросов. В начале каждой строки дано одно целое число \(x_i\) (\(1 \le x_i \le 2\)) — тип запроса.

1. Если \(x_i = 1\), то далее идет два целых числа \(v\) и \(t_{new}\) (\(1 \le v, t_{new} \le n\)) — номер города, у которого меняется провинция, и номер его новой провинции.

2. Если \(x_i = 2\), то далее идут целые числа \(t\) и \(k\), и \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le t, k, a_i \le n\)) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все \(a_i\) различны. Также гарантируется, что сумма \(k\) по всем запросам второго типа не превышает \(200\,000\).

Формат выходных данных
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Примечание
В первом запросе караваны идут из городов с номерами \(3\) и \(4\) и нужно ограбить их в городе из третьей провинции. Это те же самые города с номерами \(3\) и \(4\), через каждый из которых пройдет по одному каравану. Поэтому разбойники ограбят караваны в третьем городе и получат \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

Во втором запросе караваны также идут из городов с номерами \(3\) и \(4\), но теперь нужно ограбить их в городе из первой провинции. В первой провинции находятся города \(1\) и \(2\), через каждый из которых пройдет два каравана. Среди них разбойники выбирают город \(2\), потому что \(c_2 > c_1\) и ответ на этот запрос равен \(c_2 \cdot 2 = 3 \cdot 2 = 6\).

В третьем провинция для города \(3\) изменяется на \(1\).

В четвертом запросе караваны снова идут из городов с номерами \(3\) и \(4\), и нужно ограбить караваны в городе из первой провинции. То есть разбойники могут ограбить караваны в одном из городов с номерами \(1, 2\) или \(3\). Через города с номерами \(1\) и \(2\) пройдет два каравана, а через город \(3\) только один. Разбойникам выгодно ограбить караваны в городе \(3\) и получить \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

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

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

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

Формат входных данных
Первая строка ввода содержит целая число \(n\) — количество призов (\(1 \le n \le 1000\)). Вторая строка содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) — стоимости призов в том порядке, в котором их покажут Мише (\(1 \le a_i \le 10^9\)).

Формат выходных данных
Выведите одно число — максимальную суммарную стоимость призов, которые может получить Миша.

Числа Фибоначчи определяются следующим образом: \(F_1 = 1\), \(F_2 = 2\), а для \(n > 2\) выполнено \(F_n = F_{n - 2} + F_{n - 1}\). Таким образом, начало последовательности чисел Фибоначчи выглядит так \(1, 2, 3, 5, 8, 13, 21, \ldots\).

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

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \le n \le 100\)).

Вторая строка ввода содержит число \(k\) (\(1 \le k \le 20\)).

Формат выходных данных
Выведите все искомые представления, по одному на строке. Разделяйте числа знаком <<+>>, не используйте пробелы.

Разбиения следует упорядочить по первому слагаемому, при равном первом слагаемом — по второму, при равных первых двух — по третьему, и так далее.