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

Центр первого города расположен в точке $$$(x_1, y_1)$$$, а центр второго города расположен в точке $$$(x_2, y_2)$$$, при этом оба города расположены над прямой $$$y = 0$$$ (то есть $$$y_1, y_2 \ge 1$$$).

Самолёт, на котором полетит Вадим, будет взлетать с взлётной полосы, расположенной на прямой $$$x = 0$$$. Самолёт взлетает в точке $$$(0, 0)$$$ по направлению взлётной полосы в сторону увеличения координаты $$$y$$$, либо же в сторону уменьшения координаты $$$y$$$, при том не меняя координату $$$x$$$.

Не более одного раза в любой момент своего полёта (в том числе в момент взлёта) самолёт может сделать поворот — полететь по прямой в произвольном направлении из текущей точки.

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

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

На основе этого явления разработчики мобильных игр придумали простую аркаду. В левом нижнем углу экрана расположен баскетбольный мяч, то есть изначально он находится в точке $$$(0,0)$$$. В любой момент пользователь может нажать на экран телефона, и если в этот момент мяч находился в точке $$$(x_0, y_0)$$$, то вне зависимости от его скорости или положения он полетит по параболе, заданной уравнением $$$y = - a(x-x_0)^2 + b(x-x_0) + y_0$$$.

Экран телефона имеет ширину $$$w$$$, поэтому если мяч в какой-то момент окажется в точке вида $$$(w, y)$$$, то он мгновенно телепортируется в точку $$$(0, y)$$$, сохранив при этом свой вектор-скорости. То есть после телепорта траектория шара не изменится, и он продолжит движение по той же параболе, но смещенной на $$$w$$$ единиц влево (см. рисунок)

Пример траектории полета мяча

Баскетбольный мяч в игре отличается от обычного тем, что не отскакивает от пола и не катается по нему. Вычислите, за какое минимальное количество нажатий по экрану игрок может добиться того, чтобы мяч оказался в точке $$$(x_b, y_b)$$$.

Обратите внимание, что игрок может нажимать на экран в любой момент времени, в том числе в момент времени, когда мяч располагается в нецелых точках или когда $$$x=0$$$.

Назовем битовой характеристикой целого положительного числа $$$n$$$ количество пар целых чисел $$$i$$$ и $$$j$$$ ($$$1 \le i \lt j$$$) таких, что $$$i \oplus j = n$$$$$$^{\text{∗}}$$$ и $$$i \lor j = n$$$$$$^{\text{†}}$$$.

Вычислите значение битовой характеристики данного числа $$$n$$$.

В стране $$$N$$$ вплотную занялись образованием граждан. Президент страны считает, что абсолютно все люди должны изучать что-то новое, даже студенты университета BOPEN SUIR.

Университет можно представить как таблицу из аудиторий на $$$n$$$ строк и $$$m$$$ столбцов, где в аудитории из $$$i$$$ строки и $$$j$$$ столбца проживает очередной студент. Было принято решение провести ровно $$$q$$$ лекций. На каждой лекции будет рассказываться уникальный материал, которого нет ни на какой другой лекции. $$$i$$$-я лекция задаётся четырьмя параметрами $$$lx_i, ly_i, rx_i, ry_i$$$ ($$$1\le lx_i \le rx_i \le n, 1\le ly_i \le ry_i \le m$$$). Такая лекция будет слышна только из аудиторий, находящихся в прямоугольнике, заданном этими четырьмя числами. Иными словами, студент из аудитории $$$(x, y)$$$ услышит лекцию $$$i$$$ тогда и только тогда, когда $$$lx_i \le x \le rx_i, ly_i \le y \le ry_i$$$.

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

Самолеты-самолеты-самолеты. Тут нет самолетов, но зато есть интересная задача, которую предлагаем вам решить.

Дан массив $$$a_1, a_2, \ldots, a_n$$$. Отрезок $$$l, r$$$ ($$$1 \leq l \leq r \leq n$$$) называется хорошим, если выполняется следующее условие:

Для каждого $$$i$$$ от $$$1$$$ до $$$r - l + 1$$$ найдется такое $$$j$$$ ($$$l \leq j \leq r$$$), что $$$a_j = x^i$$$ для какого-то целого числа $$$x$$$.

Требуется сказать, сколько существует хороших отрезков.

Как известно, «БГУИР» состоит из входа, а также $$$n - 1$$$ аудиторий, пронумерованных целыми числами от $$$2$$$ до $$$n$$$, а вход имеет номер $$$1$$$. Также в университете есть $$$m$$$ коридоров, соединяющие различные аудитории, либо же вход с аудиторией. При том логично, что из входа можно добраться до любой другой аудитории, перемещаясь по коридорам университета.

Саша впервые оказался в этом замечательном университете и хочет добраться до лекционных аудиторий, чтобы узнать много нового. Но «БГУИР» не маленький, поэтому за первый день он может пройти не более чем по $$$k$$$ коридорам. Но так как за день Саша узнает много нового, то после каждого дня он может пройти на один коридор больше. Таким образом, на второй день Саша может пройти не более $$$k + 1$$$ коридор, в третий $$$k + 2$$$ и так далее.

Но пока Саша слушает интересные лекции, «БГУИР» развивается семимильными шагами. А точнее, ночью каждого дня, посередине каждого коридора образуется еще одна аудитория $$$a$$$. Так, если коридор соединял аудитории ($$$v, u$$$), то на утро коридор между этими аудиториями ликвидируют, а на его место появляются два новых ($$$v, a$$$) и ($$$a, u$$$). При том для каждого коридора аудитория по середине является уникальной, а все коридоры ликвидируют одновременно.

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

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

В языке, который использует Вадим, существует четыре операции:

• 1 $$$a$$$ — создать переменную с названием $$$a$$$.
• 2 $$$b$$$ $$$a$$$ — создать Read-only ссылку с названием $$$b$$$ на переменную с названием $$$a$$$.
• 3 $$$b$$$ $$$a$$$ — создать Writable ссылку с названием $$$b$$$ на переменную с названием $$$a$$$.
• 4 $$$a$$$ — удалить переменную либо ссылку с названием $$$a$$$.

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

1. На каждую переменную может ссылаться только один вид ссылок, но не два одновременно:
   • одна или более Read-only ссылок;
   • ровно одна Writable ссылка.
2. Каждая ссылка ссылается на существующую переменную (неудаленную).

Есть $$$n$$$ аэропортов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. У каждого аэропорта есть свой класс обслуживания, для $$$i$$$-го аэропорта это некоторое целое число $$$a_i$$$.

Авиакомпания «Беда» осуществляет авиаперелёты с соблюдением особых условий, необходимых для поддержания высокого качества обслуживания. Так, из аэропорта $$$x$$$ существует перелёт только в следующие аэропорты:

• В аэропорт $$$y$$$, такой что $$$y \gt x$$$ и $$$a_y \gt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$x \lt z \lt y$$$ и $$$a_z \gt a_x$$$.
• В аэропорт $$$y$$$, такой что $$$y \gt x$$$ и $$$a_y \lt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$x \lt z \lt y$$$ и $$$a_z \lt a_x$$$.
• В аэропорт $$$y$$$, такой что $$$y \lt x$$$ и $$$a_y \gt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$y \lt z \lt x$$$ и $$$a_z \gt a_x$$$.
• В аэропорт $$$y$$$, такой что $$$y \lt x$$$ и $$$a_y \lt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$y \lt z \lt x$$$ и $$$a_z \lt a_x$$$.

Вас интересуют $$$q$$$ запросов $$$l_i, r_i$$$ таких, что $$$1 \le l_i \le r_i \le n$$$ на покупку абонемента, позволяющего не платить за перелёт, если номера обоих аэропортов находятся в промежутке от $$$l_i$$$ до $$$r_i$$$ включительно. Выгода такого абонемента определяется как количество различных групп аэропортов с номерами в промежутке от $$$l_i$$$ до $$$r_i$$$ включительно, внутри которых можно бесплатно перемещаться. Два аэропорта $$$x$$$ и $$$y$$$ находятся в одной группе, если существует бесплатный маршрут как из $$$x$$$ в $$$y$$$, так и из $$$y$$$ в $$$x$$$. Для каждого запроса требуется определить выгоду абонемента.

К Саше на день рождения пришло $$$5$$$ друзей и принесли с собой следующие подарки:

• Кирилл подарил Саше клеточное поле $$$n \times m$$$;
• Филипп подарил $$$a$$$ одноклеточных квадратов;
• Аня подарила $$$b$$$ прямоугольников размером $$$1 \times 2$$$;
• Юра подарил Саше $$$c$$$ уголков из трех клеток и $$$c$$$ прямоугольников $$$1 \times 3$$$;
• Большой горилл подарил Саше $$$d$$$ квадратов $$$2 \times 2$$$.

При этом друзья заранее договорились о подарках, а поэтому гарантируется, что $$$a + 2b + 3c + 4d = n \cdot m$$$. Саша до этого хвастался друзьям, что умеет вкладывать в любой прямоугольник максимальное количество уголков, а поэтому друзья решили проверить навыки Саши, но уже задав ему новую задачку:

Саше требуется полностью покрыть прямоугольник $$$n \times m$$$ фигурами, которые подарили друзья, при этом он должен использовать все $$$a$$$ фигурок Филиппа, все $$$b$$$ фигурок Ани, какие-то $$$c$$$ фигурок Юры и все фигурки большого горилла.

Помогите Саше и напишите программу, которая решает поставленную задачу или определяет, что решения не существует.

На собеседовании в одну крупную авиакомпанию в качестве испытания кандидату предлагают сыграть в особые шахматы. Здесь шахматное поле представлено в виде неориентированного графа, состоящего из $$$n$$$ вершин, соединенных $$$m$$$ ребрами двух цветов — белого и черного. В вершинах с номерами $$$k$$$ и $$$q$$$ расположены фигуры короля и ферзя соответственно. Кандидат может выбрать, за какую фигуру он будет играть, а собеседующий выберет оставшуюся. Игроки выполняют ходы поочередно, первым ходит игрок, играющий за фигуру $$$X$$$. За один ход король может перемещаться в любую вершину, соединенную ребром с текущей, а ферзь может перемещаться в любую вершину, до которой существует путь из текущей вершины, состоящий из ребер одного цвета. Побеждает игрок, после хода которого фигуры оказались в одной вершине. Если побеждает кандидат, то собеседование считается пройденным.

Теперь вы интересуетесь для некоторых конфигураций игры $$$k$$$, $$$q$$$ и $$$X$$$, за какую фигуру нужно играть, чтобы гарантировать победу и, естественно, успешное прохождение собеседования.

Дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и целое число $$$k$$$. А также $$$q$$$ запросов изменения массива: заменить $$$i$$$-й элемент массива $$$a$$$ на $$$x$$$.

После каждого запроса, а также для исходного массива, нужно сказать, чему равно максимальное значение $$$a_i + a_j$$$, где $$$1 \leq i \lt j \leq n$$$, $$$j - i \lt k$$$, а также сколько таких пар $$$(i, j)$$$, дающих максимальное значение, существует.

Обратите внимание, что в этой задаче необходимо отвечать на запросы в «онлайне».

Проиграв все деньги на подарок, Саша решил подарить другой подарок, а точнее — помочь своей девушке со следующим домашним заданием:

Определим функцию $$$f(x) = (x \wedge (x + 1)) \oplus (x \wedge (x - 1))$$$.

Где $$$\wedge$$$ означает операцию побитового И, а $$$\oplus$$$ означает операцию побитового исключающего ИЛИ.

Определим функцию $$$g(x)$$$, равную количеству $$$y$$$ ($$$1 \leq y \leq 2^n - 1$$$), для которых выполняется $$$f(y) = x$$$.

Также дано число $$$a$$$ ($$$0 \leq a \leq 2^n - 1$$$). Требуется найти максимальное значение $$$a \oplus g(x)$$$.

Помогите Саше сделать приятно своей девушке и решите за него ее домашнюю работу.

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

На олимпиаде была ровно одна задача — дана перестановка чисел от $$$1$$$ до $$$n$$$: $$$p_1, p_2, \ldots, p_n$$$. Нужно узнать, какое минимальное раз можно поменять местами соседние элементы, чтобы перестановка стала отсортированной в порядке возрастания.

Но Мадока решила её следующим образом: $$$k + \frac{|1 - p_1| + |2 - p_2| + \ldots + |n - p_n|}{2}$$$. Так как жюри знает, кто отец Мадоки, то, чтобы не потерять работу, они должны сделать такие тесты, чтобы решение Мадоки было верным. И поэтому им стало интересно, сколько существует перестановок длины $$$n$$$, для которых решение Мадоки выведет верный ответ на задачу, но так как ответ на задачу может быть слишком большим, то выведите его по модулю $$$10^9 + 7$$$.