You are given a graph consisting of $$$n$$$ vertices numbered with integers from $$$1$$$ to $$$n$$$, connected by $$$n+m$$$ edges. The first $$$n$$$ edges connect neighboring vertices, meaning the $$$i$$$-th edge connects the $$$i$$$-th and $$$(i+1)$$$-th vertices, and the $$$n$$$-th edge connects the $$$n$$$-th and $$$1$$$-st vertices. In some vertices, there are $$$n-2$$$ tokens numbered with integers from $$$1$$$ to $$$n-2$$$, and no vertex can have more than one token.

In one move, you are allowed to move any token to a vertex connected by an edge to its current vertex, provided that there is currently no token in that vertex. For each token, you know which vertex it should end up in after all moves are completed.

Your task is to determine the sequence of moves so that the tokens end up in the required positions. Note that minimizing the number of moves is not required.

As is known, the airline "Trouble" often loses luggage, and concerned journalists decided to calculate the maximum number of luggage pieces that may not return to travelers.

The airline "Trouble" operates flights between $$$n$$$ airports, numbered from $$$1$$$ to $$$n$$$. The journalists' experiment will last for $$$m$$$ days. It is known that at midnight before the first day of the experiment, there were $$$s_j$$$ lost pieces of luggage in the $$$j$$$-th airport. On the $$$i$$$-th day, the following occurs:

• In the morning, $$$2n$$$ flights take off simultaneously, including $$$n$$$ flights of the first type and $$$n$$$ flights of the second type.
  • The $$$j$$$-th flight of the first type flies from airport $$$j$$$ to airport $$$(((j-2) \bmod n )+ 1)$$$ (the previous airport, with the first airport being the last), and it can carry no more than $$$a_{i,j}$$$ lost pieces of luggage.
  • The $$$j$$$-th flight of the second type flies from airport $$$j$$$ to airport $$$((j \bmod n) + 1)$$$ (the next airport, with the last airport being the first), and it can carry no more than $$$c_{i,j}$$$ lost pieces of luggage.
• In the afternoon, a check of lost luggage is conducted at the airports. If after the flights have departed on that day, there are $$$x$$$ pieces of luggage remaining in the $$$j$$$-th airport and $$$x \ge b_{i, j}$$$, then at least $$$x - b_{i, j}$$$ pieces of luggage are found, and they cease to be lost.
• In the evening, all $$$2n$$$ flights conclude, and the lost luggage transported that day arrives at the corresponding airports.

For each $$$k$$$ from $$$1$$$ to $$$m$$$, the journalists want to know the maximum number of lost pieces of luggage that may be unfound during the checks over the first $$$k$$$ days. Note that for each $$$k$$$, these values are calculated independently.

Boy Vasya loves to travel very much. In particular, flying in airplanes brings him extraordinary pleasure. He was about to fly to another city, but the runway was heavily covered with snow and needed to be cleared.

The runway can be represented as $$$n$$$ consecutive sections numbered from $$$1$$$ to $$$n$$$. The snowstorm was quite strong, but it has already stopped, so Vasya managed to calculate that the $$$i$$$-th section is covered with $$$a_i$$$ meters of snow. For such situations, the airport has a snowplow that works in a rather unusual way. In one minute, the snowplow can do the following:

• Choose a consecutive segment of length no more than $$$d$$$ and remove one meter of snow from the most snow-covered sections.

  Formally, one can choose $$$1 \le l \le r \le n$$$ ($$$r - l + 1 \le d$$$). After that, $$$c = \max \{ a_l, a_{l + 1}, \ldots , a_r \}$$$ is calculated, and if $$$c \gt 0$$$, then for all $$$i \colon l \le i \le r$$$ such that $$$a_i = c$$$, the value of $$$a_i$$$ is decreased by one.

Vasya has been preparing for the flight for a long time and wants to understand how much time he has left to wait until all sections are completely cleared of snow. In other words, it is required to calculate the minimum number of minutes that the snowplow will need to achieve $$$a_i = 0$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$.

Sasha wants to buy an apartment on a street where the houses are numbered from $$$1$$$ to $$$10^9$$$ from left to right.

There are $$$n$$$ bars on this street, located in houses with numbers $$$a_1, a_2, \ldots, a_n$$$. Note that there might be multiple bars in the same house, and in this case, these bars are considered distinct.

Sasha is afraid that by the time he buys the apartment, some bars may close, but no more than $$$k$$$ bars can close.

For any house with number $$$x$$$, define $$$f(x)$$$ as the sum of $$$|x - y|$$$ over all open bars $$$y$$$ (that is, after closing some bars).

Sasha can potentially buy an apartment in a house with number $$$x$$$ (where $$$1 \le x \le 10^9$$$) if and only if it is possible to close at most $$$k$$$ bars so that after that $$$f(x)$$$ becomes minimal among all houses.

Determine how many different houses Sasha can potentially buy an apartment in.

Every airport has a baggage claim area, and Balbesovo Airport is no exception. At some point, one of the administrators at Sheremetyevo came up with an unusual idea: to change the traditional shape of the baggage claim conveyor from a carousel to a more complex form.

Suppose that the baggage claim area is represented as a rectangular grid of size $$$n \times m$$$. The administration proposed that the path of the conveyor should pass through the cells $$$p_1, p_2, \ldots, p_{2k+1}$$$, where $$$p_i = (x_i, y_i)$$$.

For each cell $$$p_i$$$ and the next cell $$$p_{i+1}$$$ (where $$$1 \leq i \leq 2k$$$), these cells must share a common side. Additionally, the path must be simple, meaning that for no pair of indices $$$i \neq j$$$ should the cells $$$p_i$$$ and $$$p_j$$$ coincide.

Unfortunately, the route plan was accidentally spoiled by spilled coffee, and only the cells with odd indices of the path were preserved: $$$p_1, p_3, p_5, \ldots, p_{2k+1}$$$. Your task is to determine the number of ways to restore the original complete path $$$p_1, p_2, \ldots, p_{2k+1}$$$ given these $$$k+1$$$ cells.

Since the answer can be very large, output it modulo $$$10^9+7$$$.

The boarding process for various flights can occur in different ways: either by bus or through a telescopic jet bridge. Every day, exactly one flight is made from St. Petersburg to Minsk, and Vadim decided to demonstrate to the students that he always knows in advance how the boarding will take place.

Vadim made a bet with $$$n$$$ students, and with the $$$i$$$-th student, he made a bet on day $$$a_i$$$. Vadim wins the bet if he correctly predicts the boarding process on both day $$$a_i+1$$$ and day $$$a_i+2$$$.

Although Vadim does not know in advance how the boarding will occur, he really wants to win the bet at least with one student and convince him of his predictive abilities. Check if there exists a strategy for Vadim that allows him to guarantee success.

Some teachers work at the educational center "Sirius" while simultaneously studying at the university. In this case, the trip does not exempt them from completing their homework, so they do their homework right on the plane. Artem is one of those teachers, and he was assigned the following homework at the university.

With an arbitrary string $$$a$$$ of even length $$$m$$$, he can perform the following operation. Artem splits the string $$$a$$$ into two halves $$$x$$$ and $$$y$$$ of equal length, after which he performs exactly one of three actions:

• For each $$$i \in \left\{ 1, 2, \ldots, \frac{m}{2}\right\}$$$ assign $$$x_i = (x_i + y_i) \bmod 2$$$;
• For each $$$i \in \left\{ 1, 2, \ldots, \frac{m}{2}\right\}$$$ assign $$$y_i = (x_i + y_i) \bmod 2$$$;
• Perform an arbitrary number of operations (the same operations defined above, applied recursively) on the strings $$$x$$$ and $$$y$$$, independently of each other. Note that in this case, the strings $$$x$$$ and $$$y$$$ must be of even length.

Unfortunately, Artem fell asleep on the plane, so you will have to complete his homework. Artem has two binary strings $$$s$$$ and $$$t$$$ of length $$$n$$$, each consisting of $$$n$$$ characters 0 or 1. Determine whether it is possible to make string $$$s$$$ equal to string $$$t$$$ with an arbitrary number of operations.

We call a phone number a beautiful if it is a string of $$$10$$$ digits, where the $$$i$$$-th digit from the left is at least $$$10 - i$$$. That is, the first digit must be at least $$$9$$$, the second at least $$$8$$$, $$$\ldots$$$, with the last digit being at least $$$0$$$.

For example, 9988776655 is a beautiful phone number, while 9099999999 is not, since the second digit, which is $$$0$$$, is less than $$$8$$$.

Vadim has a beautiful phone number. He wants to rearrange its digits in such a way that the result is the smallest possible beautiful phone number. Help Vadim solve this problem.

Please note that the phone numbers are compared as integers.

You were flying in an airplane over the Vitebsk region and suddenly realized that you missed the beaver. You jumped out of the plane with a parachute and landed at point $$$A = (x_1, y_1)$$$, knowing for sure that your faithful friend the beaver is at point $$$B = (x_2, y_2)$$$.

There is also a lake in the forest, which is a circle with radius $$$r$$$, centered at the origin $$$(0, 0)$$$. You can move to any point in the forest (including swimming across the lake) at a speed of $$$1$$$, while along the lake, the beaver has built a dam, which allows you to move at a speed of $$$v$$$.

You are interested in the minimum amount of time it will take you to reach the beaver.

There is a directed graph with $$$n$$$ vertices and $$$m$$$ edges, as well as $$$k$$$ arrays $$$a_1, a_2, \ldots, a_k$$$.

A good path from vertex $$$1$$$ to vertex $$$n$$$ of length $$$s$$$ is defined as a sequence of vertices $$$p_1, p_2, \ldots, p_s$$$ ($$$1 \le s \le n$$$) that satisfies the following conditions:

• $$$1 = p_1 \lt p_2 \lt \ldots \lt p_{s-1} \lt p_s = n$$$; for any $$$i \in \{1,2,\ldots,s-1\}$$$, there is an edge from vertex $$$p_i$$$ to vertex $$$p_{i+1}$$$.
• For no pair $$$1 \le l \le r \le s$$$ and index $$$j \in \{1,2,\ldots,k\}$$$, the array $$$p_l, p_{l+1}, \ldots, p_r$$$ isn't the same as the array $$$a_j$$$.

Your task is to compute the number of good paths modulo $$$10^9+7$$$.

Vadim has long dreamed of finding a well-paid job, and then he learned that the airline "Beda" is looking for a web development engineer. However, it is rumored that this company gives very difficult tasks during interviews, so Vadim decided to send his student on a reconnaissance mission.

It turned out that during the interview, candidates are offered to solve a puzzle. On one table of size $$$n_1 \times m_1$$$, there are holes drilled, and on another table of size $$$n_2 \times m_2$$$, there are figures that represent prisms with a special sensor on the bottom.

The candidate's task is to fill each hole with one of the figures lying on the table. The additional complexity is that each hole must be completely filled, meaning it must match the shape of the figure placed in it. The correctness of the candidate's solution is checked automatically using special sensors, so the figures cannot be turned upside down. It is allowed not to use some of the figures.

The student was unable to complete the task on his own, but he managed to take two photographs of the tables from the task. Now Vadim has photographs of the task, but he, like his student, also could not complete the task. Therefore, Vadim began to suspect whether the task can be solved at all.

To verify his hypothesis, he sent you the photographs of the task and asked for your help.

The Bermuda Triangle — a mysterious area in the Atlantic Ocean where, according to rumors, ships and airplanes disappear without a trace. Some blame magnetic anomalies, others — portals to other worlds, but the truth remains hidden in a fog of mysteries.

A regular passenger flight 814 was traveling from Miami to Nassau on a clear sunny day. Nothing foreshadowed trouble until the plane entered a zone of strange flickering fog. Radio communication was interrupted, the instruments spun wildly, and flashes of unearthly light flickered outside the windows.

For simplicity, we will assume that the Bermuda Triangle and the airplane are on a plane, and the vertices of the triangle have coordinates $$$(0, 0)$$$, $$$(0, n)$$$, and $$$(n, 0)$$$. Initially, the airplane is located at the point $$$(x, y)$$$ strictly inside the Bermuda Triangle and is moving with a velocity vector $$$(v_x, v_y)$$$. All instruments have failed, so the crew cannot control the airplane.

The airplane can escape from the triangle if it ever reaches exactly one of the vertices of the triangle. However, if at any moment (possibly non-integer) the airplane hits the boundary of the triangle (but not at a vertex), its velocity vector is immediately reflected relative to that side$$$^\dagger$$$, and the airplane continues to move in the new direction.

Determine whether the airplane can ever escape from the Bermuda Triangle (i.e., reach exactly one of its vertices). If this is possible, also calculate how many times before that moment the airplane will hit the boundary of the triangle (each touch of the boundary, even at the same point, counts; crossing a vertex does not count).

$$$^\dagger$$$ Reflection occurs according to the usual laws of physics. The angle of incidence equals the angle of reflection.

Airplane-airplane-airplane-airplane-airplane. How can I write the problem statement about you? How can I fit you into a problem where there are no airplanes in sight? Airplane-airplane-airplane.

It is not difficult to understand that any airplane can be represented as a triple of numbers $$$(a,b,c)$$$. We will say that the airplane satisfies the quality certificate $$$p$$$ if the following conditions are met:

• $$$0 \le a, b, c \lt p$$$ and the numbers $$$a$$$, $$$b$$$, $$$c$$$ are pairwise distinct;
• $$$a b c - 1$$$ and $$$a + b + c$$$ are divisible by $$$p$$$.

For a prime number $$$p$$$, you need to find any triple of numbers $$$(a, b, c)$$$ that satisfies the quality certificate $$$p$$$, or state that such a triple does not exist.