Vadim loves traveling very much. This time he decided to take wonderful photographs of two cities from the airplane and publish them on social media. In order for the photographs to turn out well, the airplane must fly directly over the center of each city.

The center of the first city is located at point $$$(x_1, y_1)$$$, and the center of the second city is located at point $$$(x_2, y_2)$$$, with both cities located above the line $$$y = 0$$$ (that is, $$$y_1, y_2 \ge 1$$$).

The airplane that Vadim will fly on will take off from a runway located on the line $$$x = 0$$$. The airplane takes off from point $$$(0, 0)$$$ in the direction of the runway towards increasing $$$y$$$ coordinates, or towards decreasing $$$y$$$ coordinates, while keeping the $$$x$$$ coordinate unchanged.

The airplane can make a turn no more than once at any moment during its flight (including at the moment of takeoff) — flying in a straight line in any direction from its current point.

Vadim is interested in whether he will be able to take successful photographs of the two cities. Please note that he can fly over the cities in any order.

As known from school physics, if a physical point is given a velocity vector, then in an environment with a constant acceleration due to gravity, this physical point will fly along a parabola.

Based on this phenomenon, mobile game developers came up with a simple arcade game. In the lower left corner of the screen, there is a basketball, which initially is at the point $$$(0,0)$$$. At any moment, the user can tap the screen of the phone, and if at that moment the ball is at the point $$$(x_0, y_0)$$$, then regardless of its speed or position, it will fly along a parabola defined by the equation $$$y = - a(x-x_0)^2 + b(x-x_0) + y_0$$$.

The phone screen has a width of $$$w$$$, so if the ball at any moment is at a point of the form $$$(w, y)$$$, it will instantly teleport to the point $$$(0, y)$$$, while preserving its velocity vector. That is, after the teleportation, the trajectory of the ball will not change, and it will continue to move along the same parabola, but shifted $$$w$$$ units to the left (see the figure).

Example trajectory of the ball

The basketball in the game differs from a regular one in that it does not bounce off the ground and does not roll on it. Calculate the minimum number of taps on the screen that the player needs to make in order for the ball to reach the point $$$(x_b, y_b)$$$.

Note that the player can tap the screen at any moment in time, including at the moment when the ball is at non-integer points or when $$$x=0$$$.

We define the bitwise characteristic of a positive integer $$$n$$$ as the number of pairs of integers $$$i$$$ and $$$j$$$ ($$$1 \le i \lt j$$$) such that $$$i \oplus j = n$$$ and $$$i \mid j = n$$$.

Calculate the value of the bitwise characteristic of the given integer $$$n$$$.

$$$\oplus$$$ denotes the bitwise XOR operation.

$$$\mid$$$ denotes the bitwise OR operation.

В стране $$$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$$$, за какую фигуру нужно играть, чтобы гарантировать победу и, естественно, успешное прохождение собеседования.

Given an array of integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$. There are also $$$q$$$ queries to modify the array: replace the $$$i$$$-th element of the array $$$a$$$ with $$$x$$$.

After each query, as well as for the initial array, you need to determine the maximum value of $$$a_i + a_j$$$, where $$$1 \leq i \lt j \leq n$$$, $$$j - i \lt k$$$, and how many such pairs $$$(i, j)$$$ exist that yield the maximum value.

Note that in this problem, you need to respond to queries in "online" mode.

Having lost all the money for a gift, Sasha decided to give a different gift, specifically — to help his girlfriend with her homework:

Let's define the function $$$f(x) = (x \wedge (x + 1)) \oplus (x \wedge (x - 1))$$$.

Where $$$\wedge$$$ denotes the bitwise AND operation and $$$\oplus$$$ denotes the bitwise XOR opearation.

Let's define the function $$$g(x)$$$ as the number of $$$y$$$ ($$$1 \leq y \leq 2^n - 1$$$) for which $$$f(y) = x$$$ holds true.

Also given is the number $$$a$$$ ($$$0 \leq a \leq 2^n - 1$$$). It is required to find the maximum value of $$$a \oplus g(x)$$$.

Help Sasha please his girlfriend and solve her homework for her.

Madoka has already finished writing the municipal stage in Novosibirsk and went home to wait for the results of the closed testing.

At the olympiad, there was exactly one problem — given a permutation of numbers from $$$1$$$ to $$$n$$$: $$$p_1, p_2, \ldots, p_n$$$. It is necessary to find out the minimum number of times one can swap adjacent elements to sort the permutation in ascending order. However, Madoka solved it as follows: $$$k + \frac{|1 - p_1| + |2 - p_2| + \ldots + |n - p_n|}{2}$$$.

But since the jury knows who Madoka's father is, in order not to lose their job, they must create tests such that Madoka's solution is correct. Therefore, they became interested in how many permutations of length $$$n$$$ exist for which Madoka's solution will yield the correct answer to the problem, but since the answer may be too large, output it modulo $$$10^9 + 7$$$.