Делать задачи сложно. Поэтому Влад пошел играться с ежами в кубики. У него было 2 вида кубиков, на $$$x$$$ кубиках нарисованы буквы A, на $$$y$$$ кубиках буквы C. Он придумал треугольник ACC, по принципу треугольника Паскаля. На $$$i$$$-м слое $$$(i \gt 0)$$$ треугольника АСС должна находиться ровно одна буква А и ровно $$$i-1$$$ букв С следующих за ней.

пример треугольника ACC высоты 4

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

Это интерактивная задача.

Задан отсортированный в неубывающим порядке массив $$$a$$$ длины $$$n$$$. Элементы массива не превосходят $$$n$$$. Вам известна только длина массива. Используя не более чем $$$2 \cdot n$$$ запросов, необходимо отгадать весь массив. Запросы можно выполнять следующего типа: «? i x», где $$$1 \leq i \leq n$$$ и $$$x$$$ — целое число. Жюри ответит следующим образом:

• = если $$$a_i = x$$$,
• > если $$$x \gt a_i$$$,
• < если $$$x \lt a_i$$$.

После того как вы определите массив, вы должны вывести его следующим образом: «! $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$», где $$$a_1, a_2, \ldots, a_n$$$ — это элементы массива, которые вы угадали.

1. Выведите запросы в формате «? i x».
2. Жюри ответит одним из трех символов: «=» если $$$a_i = x$$$, «>» если $$$x \gt a_i$$$, или «<» если $$$x \lt a_i$$$.
3. Выведите ответ в формате «! $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$».

Недавно Максим прилетел в Корею и захотел попасть на фестиваль фейерверков в Пусане.

Система поездов Кореи представляет собой дерево из $$$n$$$ вершин. Пути поездов двусторонние, и для каждой поездки нужно потратить $$$1$$$ билет.

Максим начинает свой путь из вершины $$$1$$$ и должен попасть в вершину $$$n$$$. Находясь в вершине $$$i$$$ можно купить любое количество билетов по $$$a_i$$$ вон.

Найдите минимальное количество вон, необходимое, чтобы Максим попал в вершину $$$n$$$ из вершины $$$1$$$.

Вам дан массив $$$a$$$ длины $$$n$$$. Тройка чисел $$$(x, y, z)$$$ называется красивой, если выполняются условия: $$$x$$$ делится на $$$y$$$ без остатка, $$$y$$$ делится на $$$z$$$ без остатка, и $$$x \gt y \gt z$$$.

Даны $$$q$$$ запросов вида $$$(l, r)$$$. Необходимо для каждого запроса найти такие индексы $$$i \lt j \lt k$$$ в массиве $$$a$$$, что тройка $$$(a_i, a_j, a_k)$$$ является красивой и $$$l \leq i \lt j \lt k \leq r$$$. Из всех таких троек выбрать ту, которая максимизирует значение $$$n^2 \cdot a_i + n \cdot a_j + a_k$$$. Если существует несколько троек с максимальным значением, выбрать лексикографически минимальную тройку $$$(i, j, k)$$$.

Shenfe1 во время РО 2023 случайно попал на поляну ежей. Изначально на поляне нет ни одного ежа. Каждый из $$$n$$$ ($$$1 \leq n \leq 300$$$) ежей имеет три характеристики. $$$i$$$-й еж имеет три характеристики: $$$L_i$$$ ($$$1 \leq L_i \leq 10^8$$$), $$$C_i$$$ ($$$-10^8 \leq C_i \leq 10^8$$$) и скорость. Если $$$i \lt j$$$, то еж под номером $$$i$$$ быстрее ежа под номером $$$j$$$. Так же, гарантируется, что все $$$L_i$$$ уникальны.

В $$$L_i$$$-ю минуту еж $$$i$$$ приходит на поляну, и если он все еще на поляне, то через $$$T$$$ ($$$1 \leq T \leq 10^8$$$) минут он уйдет. Обратите внимание, все ежи находятся на поляне одинаковое количество времени, и что $$$i$$$-й еж еще будет находиться на поляне в момент времени $$$L_i + T$$$.

Shenfe1 может в любой момент времени, если на поляне есть хотя бы один еж, кинуть им еду. В таком случае, если на поляне $$$i$$$-й еж — самый быстрый еж, то он забирает еду и уходит, а к настроению Shenfe1 добавляется $$$C_i$$$ раздраженности. Временем броска еды, подбором еды и прихода/ухода ежа можно пренебречь.

Shenfe1 хочет знать, какую максимальную раздраженность в самом худшем случае он может получить, если изначально его раздраженность равна 0.

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

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

Для прояснения, допустим, что последний раз он ел в час под номером $$$x$$$. Тогда, если с момента времени $$$x+1$$$ и до момента времени $$$x+b$$$ включительно он не поест, то Миним умрет, и будет очень грустно... Со сном аналогично.

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

Во время составления задач турнира злой злодей Башкиров Даниил заточил всех членов жюри в клетки. Для коммуникации из каждой клетки есть односторонний туннель в одну другую. Изначально $$$i$$$-й член жюри сидит в клетке $$$i$$$. Но чтобы дело шло эффективно, нужно, чтобы каждый член жюри хорошо питался. Для этого Даниил поручил Леба Нону одно задание — накормить всех членов жюри. Для этого Леба Нон решил организовать $$$q$$$ обедов. Каждый обед проводится в одной из клеток. Если член жюри может дойти до клетки с обедом, то он идет в нее и не возвращается обратно. Расстояние между клетками - это количество туннелей, которые составляют путь между ними. Помогите Леба Нону посчитать суммарное расстояние, которое пройдет каждый член жюри.

Как оказалось, Railgun обожает задачи на геометрию. Его наставник в этом деле, fractal, дал ему множество из $$$N$$$ точек на плоскости, некоторые из них можно сделать анимешными. Особенность анимешной точки (условно $$$H$$$) в том, что имея произвольную точку $$$P$$$, можно за одну операцию превратить ее в точку $$$P'$$$, повернув относительно $$$H$$$ на какой-либо угол. Иными словами, если описать окружность $$$\omega$$$ вокруг точки $$$H$$$ радиуса $$$dist(H, P)$$$, то должно выполняться $$$P' \in \omega$$$.

Также fractal дал ему $$$Q$$$ независимых запросов: имея произвольную точку $$$A(x, y)$$$, сказать, возможно ли из нее перейти в точку $$$B(-x, -y)$$$, вращая ее вокруг анимешных точек. Изначально у Railgun нет анимешных точек. А так как делать их долго, он попросил вас сказать наименьшее количество анимешных точек, которые ему пригодятся (если, конечно, запрос fractal осуществим). А так же сказать сколько существует способов выбрать их. Так как это число может быть большим, он попросил вывести его по модулю $$$10^9 + 7$$$.

Количество операций минимизировать не нужно.

fractal любит геометрию, по этому поместим его в привычное ему пространство, двумерную плоскость. Изначально, fractal находится в координате O(0, 0) и смотрит в сторону оси Ox. Ему дали задание, листок и четное число $$$n$$$ $$$(4 \le n \le 10^6)$$$, зачем и почему мало кто знает, но такова судьба. Ему необходимо выполнить ровно n операций, каждая операция происходит следующим образом:

• fractal выбирает любое положительное целое число X.
• Постепенно пройти на X клеток напрямую вперед в сторону, в которую он сейчас смотрит.
• Повернуть либо направо, либо налево и записать выбранный поворот на листок.

Если после выполнения всех операций, fractal оказался в координате O(0, 0) и смотрит в сторону оси Ox, а так же никогда, кроме самого последнего момента последней операции, не был в координате, которую он посещал раньше, то полученная запись на листке будет называться как «ответ» на задание.

Но так как fractal любит все считать и числа Каталана, он захотел посчитать, сколько «ответов» он сможет получить. Так как ответ может быть очень большим, выведите его по модулю $$$10^9 + 7$$$.

В далеком будущем, в галактике под управлением Звездного Союза, межзвездные корабли и планеты образуют сложную сеть, являющуюся деревом. Эта сеть состоит из $$$n$$$ вершин. Союз сталкивается с серьезной угрозой — $$$m$$$ типов кибер-вирусов, которые могут быстро распространяться через сеть и заражать все планеты и корабли.

Каждый из $$$m$$$ типов кибер-вирусов обладает уникальными свойствами и может заражать соседние вершины в сети. В момент времени $$$t$$$, если планета или корабль $$$v$$$ заражены вирусом типа $$$i$$$, то в момент времени $$$t + 1$$$ все соседние вершины также будут заражены этим вирусом. Задача Звездного Союза — контролировать и отслеживать распространение вирусов, чтобы предотвратить катастрофические последствия.

Звездный Союз создал командный центр для управления распространением кибер-вирусов. К ним поступают запросы трех типов:

1. Внедрение вируса:

   В момент времени $$$time$$$ вершина $$$v$$$ заражается кибер-вирусом типа $$$i$$$. Важно отметить, что каждый кибер-вирус типа $$$i$$$ уникален, и моменты времени $$$time$$$ не обязательно возрастают.

2. Удаление вируса:

   Нужно удалить кибер-вирус типа $$$i$$$, что означает, что этот вирус больше не учитывается при анализе.

3. Анализ заражений:

   Нужно определить минимальное время $$$t$$$, когда найдется вершина, которая заражена всеми не удаленными кибер-вирусами на отрезке $$$[l, r]$$$, то есть такая вершина $$$v$$$, что она заражена всеми вирусами на отрезке. Также необходимо вывести все вершины, которые будут заражены каждым кибер-вирусом из этого диапазона в момент $$$t$$$.

Изначально ни одна из вершин не заражена никаким вирусом.

ААлихан и $$$k$$$ его друзей собираются пойти на концерт AAdo. Концертный зал можно представить в виде таблицы из $$$n$$$ строк и $$$m$$$ столбцов(цена на место в строке $$$i$$$ и столбце $$$j$$$ равна $$$c_{i,j}$$$), где первая строка стоит ближе всего к сцене, а последняя дальше всего от сцены. Каждая клетка таблицы является одним местом. Места внутри одного столбца стоят по убыванию цены от первой строки к последней (чем ближе к сцене, тем дороже). Можно считать, что сцена находится на строке $$$0$$$. ААлихан и его друзья хотят купить по одному месту каждый так, чтобы суммарно потратить не больше $$$B$$$ бетабаксов и их места образовывали одну компоненту связности. Также они все мечтают увидеть лицо AAdo, поэтому они хотят сесть так, чтобы самый дальний из друзей был как можно ближе к сцене. Найдите ряд самого дальнего друга.

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

Гарантируется, что у ААлихана всегда будет способ купить $$$k+1$$$ место.