Студент четвертого курса МИСИС Владислав получил задание напечатать логотипы VK для олимпиады «Когнитивные технологии». Программа для печати, которой решил воспользоваться Владислав, оказалась необычной и могла работать только с отрезками прямых. В связи с этим Владислав разработал свой дизайн логотипа, в котором используются только отрезки.

Для универсальности Владислав ввел параметр $$$h$$$, который задает высоту логотипа, где $$$3 \le h \le 10^5$$$. При этом ширина логотипа всегда равна пяти. На рисунке приведена схема того, как выглядит логотип высоты $$$h$$$ на клетчатом поле. На рисунке формула $$$[h / 2]$$$ обозначает целую часть с округлением вниз. Также на рисунке приведены примеры логотипов с высотой $$$h = 3$$$ и $$$h = 4$$$.

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

Дано дерево, состоящее из $$$n$$$ вершин, пронумерованных числами от $$$1$$$ до $$$n$$$. У каждой вершины $$$v$$$ кроме корневой непосредственный предок равен $$$p_v$$$, если $$$v$$$ — корень, то выполняется $$$p_v = v$$$. Вершина $$$u$$$ называется предком $$$v$$$, если $$$u$$$ содержится на простом пути от $$$v$$$ до корня дерева. В частности, сама вершина, ее непосредственный предок и корень всегда являются ее предками.

Пусть $$$S$$$ — некоторое множество вершин дерева, обозначим через $$$\textrm{LCA}(S)$$$ наименьшего общего предка множества $$$S$$$, то есть наиболее удаленную от корня вершину, которая является предком для каждой вершины из $$$S$$$.

Например, пусть дерево состоит из $$$6$$$ вершин и имеет вид как на картинке выше. Тогда:

• $$$\textrm{LCA}(\{2, 3\}) = 5$$$
• $$$\textrm{LCA}(\{6, 1\}) = 1$$$
• $$$\textrm{LCA}(\{5, 2, 3\}) = 5$$$
• $$$\textrm{LCA}(\{3\}) = 3$$$

Требуется узнать сумму значений номеров наименьших общих предков для всех непустых подмножеств вершин дерева. Так как ответ может быть слишком большим, выведите его по модулю $$$10^9 + 7$$$

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

Фотоальбом представляет собой прямоугольник $$$n \times m$$$, где в каждой клетке содержится ровно одна фотография. Также для каждой фотографии известно, есть ли на ней попуг. Мадока может вырезать только подпрямоугольники фотоальбома. Но при том вырезанные подпрямоугольники не могут пересекаться или касаться по сторонам.

Так, например, следующие прямоугольники нельзя вырезать, так как они касаются по стороне:

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

Для подготовки к олимпиаде «Когнитивные Технологии» Мадока решила все задачи в мире на сортировки перестановок. Но жюри смогли удивить ее, и дали задачу, которую она нигде до этого не видела, и она не смогла решить ее. Вот она:

Дана перестановка $$$p_1, p_2, \ldots, p_n$$$. С ней можно выполнять следующую операцию:

• выбрать пару различных индексов $$$i, j$$$ ($$$1 \le i, j \le n$$$), где $$$p_i = 1$$$ и $$$|i - j| \le \frac{n}{2}$$$
• поменять местами $$$p_i$$$ и $$$p_j$$$.

Нужно отсортировать перестановку не более, чем за $$$4 \cdot n$$$ операций, либо сообщить, что это невозможно.

Молодой ученый-астроном из МИСИС Виталий Олегович занимается исследованием звезд в космическом пространстве. Для своих исследований он создал модель, в которой проверяет различные гипотезы. Для очередного исследования ему понадобилась помощь программистов. Дело в том, что ему необходимо эффективно определять количество звезд внутри сферических областей пространства. Помогите молодому ученому с его задачей!

Факториалом целого положительного числа $$$n$$$ называется число $$$n! = 1 \cdot 2 \cdot \ldots \cdot n$$$.

Леопардовым называется число, представимое в виде произведения факториалов. Например, число $$$2880$$$ является леопардовым ($$$2! \cdot 2! \cdot 3! \cdot 5!$$$).

Горилловым называется число, представимое в виде суммы ровно трёх леопардовых чисел. Например, число $$$342$$$ является горилловым ($$$6 + 96 + 240$$$).

Красотой гориллового числа называется количество упорядоченных способов представить его в виде суммы трёх леопардовых чисел. Заметьте, что представления $$$6 + 96 + 240$$$ и $$$96 + 6 + 240$$$ считаются различными. Например, красота гориллового числа $$$6$$$ равна $$$4$$$ ($$$1 + 1 + 4$$$, $$$1 + 4 + 1$$$, $$$2 + 2 + 2$$$, $$$4 + 1 + 1$$$).

Вам предстоит ответить на $$$q$$$ запросов.

Каждый запрос задаёт отрезок целых чисел $$$[l \ldots r]$$$. Посчитайте сумму красот горилловых чисел $$$x$$$ на этом отрезке ($$$l \le x \le r$$$).

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

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

Мост в связном графе — это ребро, удаление которого приводит к тому, что найдутся две вершины между которыми нет пути.

Точка сочленения в связном графе — это вершина, удаление которой приводит к тому, что найдутся две вершины между которыми нет пути.

Уже завтра олимпиада, поэтому Олег считает(из своего опыта), что одного теста в задаче достаточно. Олег хочет, чтобы в единственном тесте был задан связный граф ровно с $$$k_1$$$ мостами и $$$k_2$$$ точками сочленения. Помогите Олегу.

Можно показать, что в указанных ограничениях решение всегда существует.

Вам дано клеточное поле $$$n \times m$$$. Некоторые клетки имеют углубления, в которые можно вставлять фигурки; они обозначены символом «.», остальные клетки обозначены символом «#».

Также у вас есть фигурки трех видов, которые вы можете вставлять в любые свободные клетки поля. Они изображены на рисунке ниже:

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

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

В центре Призрачного мира находится древнее дерево, известное как «Высший Разум». Это существо является связующим звеном для всех Призрачных. Каждый Призрачный представлен вершиной в графе, где ребра представляют собой связи между Призрачными.

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

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

В Призрачном мире существуют два типа запросов, которые могут быть сделаны к Высшему Разуму:

1. Запрос на добавление связи: + $$$a$$$ $$$b$$$ $$$k$$$. Этот запрос добавляет новую связь между двумя Призрачными существами с приоритетом $$$k$$$. Благодаря этому запросу, новая связь будет создана между Призрачными существами $$$a$$$ и $$$b$$$ с приоритетом $$$k$$$.

2. Запрос на поиск минимального приоритета: ? $$$p$$$. Этот запрос позволяет найти минимальный неотрицательный приоритет $$$k$$$, при котором ребра с приоритетом меньше или равном $$$k$$$, образуют ровно $$$p$$$ компонент связности в графе Призрачного мира. Если такого приоритета не существует, выводится значение $$$-1$$$.

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

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

Дан круг, состоящий из $$$2n$$$ секторов, пронумерованных от $$$1$$$ до $$$2n$$$ по часовой стрелке, начиная с некоторой точки. За сектором $$$1$$$ следует сектор $$$2$$$, за сектором $$$2$$$ — сектор $$$3$$$ и так далее, а за сектором $$$2n$$$ следует сектор $$$1$$$. Между любыми соседними$$$^{[1]}$$$ секторами можно передвигаться за $$$1$$$ единицу времени. Помимо этого, из сектора $$$i$$$ в сектор $$$j$$$, расположенный диаметрально противоположно$$$^{[2]}$$$ сектору $$$i$$$, можно сдвинуться за $$$a_i$$$ единиц времени. Заметим, что в данном случае время передвижения зависит от направления движения: $$$a_i$$$ из $$$i$$$ в $$$j$$$ и $$$a_j$$$ из $$$j$$$ в $$$i$$$.

Необходимо ответить на $$$q$$$ запросов. Каждый запрос задается двумя номерами секторов $$$u_i$$$ и $$$v_i$$$. Для каждого запроса необходимо найти минимальное количество времени, которое потребуется, чтобы попасть в сектор $$$v_i$$$, если начинать в секторе $$$u_i$$$.

$$$^{[1]}$$$ Два сектора $$$i$$$ и $$$j$$$ называются соседними, если $$$i$$$ следует сразу после $$$j$$$ или наоборот.

$$$^{[2]}$$$ Два сектора $$$i$$$ и $$$j$$$ называются диаметрально противоположными, если $$$|i - j| = n$$$.

Вы очень любите старые Java игры с кнопочных телефонов, поэтому уже давно прошли их все. Сегодня ночью вам приснилась очень интересная игра, которой никогда не существовало. Игра называлась «Приключения гуманоида 3».

В точке $$$(0, 0)$$$ бесконечного клетчатого поля находится гуманоид, которым вы управляете. В точке $$$(n, m)$$$ находится горилла, которую вы хотите навестить. Горилла очень ждёт встречи с вами, но боится заблудиться, поэтому стоит на месте.

Для управления гуманоидом доступны четыре клавиши: $$$2$$$, $$$4$$$, $$$6$$$, $$$8$$$.

• Клавиша $$$2$$$ перемещает гуманоида на одну клетку вверх $$$(x, y) \to (x, y + 1)$$$;
• Клавиша $$$4$$$ перемещает гуманоида на одну клетку влево $$$(x, y) \to (x - 1, y)$$$;
• Клавиша $$$6$$$ перемещает гуманоида на одну клетку вправо $$$(x, y) \to (x + 1, y)$$$;
• Клавиша $$$8$$$ перемещает гуманоида на одну клетку вниз $$$(x, y) \to (x, y - 1)$$$.

Вам также приснилась строка $$$s$$$, задающая последовательность клавиш. Вы помните, что выбрали ровно $$$k$$$ последовательных клавиш из $$$s$$$ и нажали их по порядку. Мог ли гуманоид добраться до гориллы или вы что-то перепутали? Считается, что гуманоид добрался до гориллы, если ровно после $$$k$$$ шагов он закончил в клетке с ней.