Том и Гек красят забор. Забор состоит из $$$a + b$$$ сегментов, при чем первые $$$a$$$ сегментов — деревянные, а оставшиеся $$$b$$$ — металлические.

Тому и Геку обещали вознаграждение за покраску забора. На деревянные и металлические сегменты тратится разное количество усилий, поэтому покраска деревянного сегмента оценивается в $$$x$$$ монет, а металлического — в $$$y$$$ монет.

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

Помогите им определить, какое должно быть их место встречи $$$k$$$, чтобы вознаграждение за покраску Тому и Геку различалось как можно меньше. Местом встречи будем считать номер последнего сегмента, который покрасит Том. Иными словами, если место встречи — $$$k$$$, Том покрасил $$$k$$$ левых сегментов, а Гек — оставшиеся $$$a + b - k$$$ правых.

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

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

Программист Лев, (почти) занимающий позицию тимлида, решил взять себе отпуск. Но поскольку его присутствие на рабочем месте и доступность могут быть критичными для команды, он разобьет этот отпуск на несколько частей: а именно, он будет на протяжении обозримого будущего жить в цикличном режиме «$$$x$$$ дней работы, затем $$$y$$$ дней отпуска».

Разумеется, у него есть запланированные совещания с командой, дни релиза новой версии и другие события, которые никак нельзя пропускать. Известно всего $$$n$$$ таких событий, и $$$i$$$-е из них запланировано на день $$$d_i$$$.

Считая, что сегодня день номер $$$1$$$, а все события запланированы не раньше, чем на день номер $$$1$$$ определите, существует ли такой день $$$D \le x + y$$$, что если в день $$$D - x - y$$$ (то есть еще до первого дня) Лев перейдет на новый режим, он не пропустит ни одно запланированное событие. Иными словами, требуется добиться того, чтобы все дни $$$d_i$$$ приходились на фазу работы в соответствующем цикле.

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

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

В этот раз Влад получил массив $$$a$$$ из $$$n$$$ целых чисел. За одну операцию Влад может выбрать любой отрезок этого массива и прибавить ко всем элементам на этом отрезке одинаковое число $$$x$$$ от $$$1$$$ до $$$k$$$ включительно.

Несмотря на то, что Влад привык работать с палиндромами, в этот раз у него возникли проблемы с тем, чтобы получить из $$$a$$$ палиндром за минимальное число действий. Помогите ему поскорее справиться с этой задачей.

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

Обратите внимание, что нет группы с $$$k = 3$$$ без каких-либо других дополнительных ограничений!

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

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

В этот раз VK организует новый хакатон, и на него на площадке проведения собрались $$$m$$$ участников. Для этих $$$m$$$ участников организаторы заказали $$$n$$$ пицц, которые на площадке расположили в ряд и пронумеровали от $$$1$$$ до $$$n$$$. Известно, что

• каждая пицца состоит из бесконечного числа кусочков;
• первый кусочек $$$i$$$-й пиццы имеет толщину теста $$$a_i$$$, а каждый следующий — на $$$1$$$ больше предыдущего (то есть $$$a_i + 1$$$, $$$a_i + 2$$$, и так далее);
• наиболее привлекательными для участников кажутся кусочки с наименьшей толщиной теста;
• любой участник может подойти к ряду с пиццами в произвольном месте, но после может перемещаться только влево (в сторону меньших номеров), чтобы не мешать другими участникам.

Периодически участники встают со своих мест и подходят к ряду пицц, чтобы взять один кусочек. Участник номер $$$i$$$ подходит к пицце с номером $$$s_i$$$ в момент времени $$$t_i$$$, после чего моментально находит кусочек пиццы с наименьшей толщиной теста среди пицц от $$$1$$$-й до $$$s_i$$$-й и начинает двигаться в его сторону. На перемещение между двумя соседними пиццами у каждого участника уходит одинаковое время — $$$v$$$ секунд. Несколько участников могут одновременно находиться около одной пиццы.

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

Формально этот процесс можно описать следующим образом. В каждое целое число секунд $$$t$$$:

1. все участники, уже стоявшие в ряду в момент времени $$$t - 1$$$, сдвигаются на $$$\frac{1}{v}$$$ влево;
2. все участники с $$$t_i = t$$$ подходят к пицце с номером $$$s_i$$$;
3. время «останавливается»;
4. определяются все участники, стоящие на таких целых позициях $$$p$$$, что $$$a_p = \min(a_1, a_2, \ldots, a_p)$$$;
5. для каждого такого $$$p$$$ участник с минимальным номером, стоящий на позиции $$$p$$$, забирает кусочек пиццы толщиной $$$a_p$$$ и уходит; $$$a_p$$$ увеличивается на $$$1$$$;
6. после того, как некоторые кусочки пицц забрали, могло случиться так, что у каких-то участников изменилась минимальная толщина кусочка, который они все еще могут получить, в таком случае процесс повторяется с шага 4;
7. иначе, время «запускается заново» и процесс переходит на следующую секунду.

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

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

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

Рассмотрим некоторое полное двоичное дерево с $$$n = 2^k$$$ листьями. Дадим корню номер $$$1$$$, его детям — номера $$$2$$$ и $$$3$$$ (слева направо), и так далее занумеруем каждый слой вершин последовательными целыми номерами. Листья дерева будут иметь номера от $$$n$$$ до $$$2n - 1$$$. У вершины номер $$$i$$$ вес равен $$$w_i$$$. Весом множества вершин мы будем называть сумму весов вершин этого множества.

Тогда от вас требуется определять, как эффективно подрезать деревья. Запрос на подрезку задается номерами листьев $$$l$$$ и $$$r$$$, и осуществляется следующим образом:

1. Сначала выбирается множество вершин $$$V$$$ — минимальное по размеру связное множество вершин, содержащее все листья с $$$l$$$-го по $$$r$$$-й. Обозначим самую близкую к корню дерева вершину множества $$$V$$$ за $$$\mathtt{root}(V)$$$.
2. Затем требуется выбрать в множестве $$$V$$$ две различные вершины $$$x$$$ и $$$y$$$ такие, что ни одна из них не является потомком другой.
3. Когда вершины $$$x$$$ и $$$y$$$ выбраны, ребра, ведущие из $$$\mathtt{root}(V)$$$, $$$x$$$ и $$$y$$$ «наверх» (в сторону корня), обрезаются. Тем самым $$$V$$$ отделяется от всего дерева, и распадается на три подмножества, обозначим их как $$$V_\mathtt{root}$$$, $$$V_x$$$ и $$$V_y$$$, соответственно.
4. После чего все три этих подмножества высаживаются в качестве отдельных поддеревьев, чтобы повысить благоустройство территории.

У руководства есть несколько вариантов, как подрезать данное вам дерево. Ваша цель — определить для каждого из их запросов $$$(l, r)$$$, какие вершины $$$x$$$ и $$$y$$$ следует выбрать, чтобы минимизировать максимальный из весов $$$V_\mathtt{root}$$$, $$$V_x$$$ и $$$V_y$$$.

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