You are an elite mercenary who has infiltrated the legendary beehive of the Queen Bee. The hive is built from regular hexagonal cells arranged in concentric layers around the queen's chamber at the center. The central cell is numbered $$$0$$$.

The hive has $$$(n + 1)$$$ layers numbered from $$$0$$$ to $$$n$$$. Layer $$$0$$$ contains only the queen's chamber (cell $$$0$$$). For every integer $$$x \: (1 \le x \le n)$$$, layer $$$x$$$ is defined as the set of cells that are adjacent to at least one cell of layer $$$(x - 1)$$$ and are not part of any smaller layer. Each layer surrounds the previous (except layer $$$0$$$) and is surrounded by the next (except layer $$$n$$$).

The cells are numbered layer by layer outward from the center. Within each layer, the numbering starts at the topmost cell of that layer. Numbering proceeds clockwise for odd-numbered layers and counter-clockwise for even-numbered layers.

You are currently at the queen's chamber at cell $$$0$$$. Your mission is to kill the queen, and then escape the beehive from cell $$$k$$$.

Every cell other than the queen's chamber houses a guard bee. If a single guard bee anywhere in the hive is alive at the moment you exit the queen's chamber, you will be detected and killed immediately. Therefore, any bee that remains alive while you leave the center is fatal.

From the queen's chamber, you can use a powerful laser gun and fire any number of shots. Each shot is a perfect straight ray that originates at the center of the queen's chamber and extends to infinity in some direction. A shot kills a guard bee if and only if the center of that bee's cell lies exactly on the line of fire. The shot must be fully precise: if the center of a cell is missed by even the smallest amount, the guard bee in that cell remains alive.

After killing the queen and all the guards, you will walk from cell $$$0$$$ to cell $$$k$$$ along adjacent cells. A path is a sequence of cells where each consecutive pair of cells is adjacent. A path from one cell to another is considered shortest if and only if it contains the minimum possible number of cells among all paths connecting those two cells. Two paths are considered different if and only if there exists at least one position where the corresponding cells of the two paths are not the same.

Because you are in a hurry to watch a football match after the mission, you need to calculate the minimum number of laser shots you need to fire and the number of distinct shortest paths from the queen's chamber back to your escape cell. As the answers can be very large, output them modulo $$$(10^9 + 7)$$$.

The government of Ajobdesh launched an ambitious project to build a national highway, spanning the entire country, costing billions of dollars. But the construction company decided that high-quality bitumen was optional and spent most of the budget on million dollar pillows. As a result, the highway is riddled with potholes and cars break down all the time. As stranded vehicles become a common sight along the highway, the tow truck business is booming.

There are $$$n$$$ tow truck companies operating on the highway. The $$$i^{th}$$$ company operates a truck which is positioned at $$$x_i$$$ and moves at speed $$$v_i$$$. If a car breaks down at position $$$y$$$, the time required to reach it for the $$$i^{th}$$$ truck is $$$\dfrac{|y-x_i|}{v_i}$$$. You want to know the minimum response time for a tow truck if a car breaks down.

You must answer $$$q$$$ queries. Each query will be one of the following two types.

• + x v — A new company opens with a truck at position $$$x$$$ with speed $$$v$$$.
• ? y — A car breaks down at position $$$y$$$. You have to find the minimum time taken by any tow truck to reach the car.

Note that the queries of the second type are independent, you can assume that all tow trucks are at their initial positions before each query.

Consider a three-dimensional grid of size $$$X \times Y \times Z$$$, representing underground layers. The $$$(x, y)$$$ plane corresponds to the horizontal surface, while the $$$z$$$-axis represents depth below the surface, with $$$z = 0$$$ denoting the topmost layer.

Each cell of the grid is of exactly one of the following two types:

• Rock: denoted by the character '#'.
• Gas: denoted by the character '.', where each gas cell contains exactly $$$1$$$ unit of gas.

A reservoir is defined as a maximal connected component of gas cells. Two gas cells are considered adjacent if and only if they share a common face. More formally, a gas cell with coordinates $$$(x, y, z)$$$ is adjacent to another gas cell if their coordinates differ by exactly $$$1$$$ in one of the three dimensions and are equal in the other two dimensions; that is, the adjacent coordinates are $$$(x \pm 1, y, z)$$$, $$$(x, y \pm 1, z)$$$, or $$$(x, y, z \pm 1)$$$.

You may dig a borehole from the surface. A borehole is defined by choosing a surface coordinate $$$(x, y)$$$ and drilling vertically downward through all depths from the top layer $$$(z = 0)$$$ to the bottom layer $$$(z = Z - 1)$$$.

During drilling, the drill passes through both rock and gas cells. Whenever the drill encounters a gas cell, it immediately collects the entire reservoir containing that cell. Drilling continues downward and may intersect multiple reservoirs at different depths. Each reservoir is collected at most once, even if the drill intersects it multiple times within the same vertical column. Each gas cell contributes exactly $$$1$$$ unit to the total collected gas.

Thus, drilling a borehole at surface coordinates $$$(x, y)$$$ collects the total amount of gas contained in all distinct reservoirs that include at least one gas cell in the vertical column $$$(x, y, 0), (x, y, 1), \dots, (x, y, Z - 1)$$$.

Your task is to determine the maximum total amount of gas that can be collected by drilling a single borehole at an optimal choice of surface coordinates $$$(x, y)$$$.

In the magical land of Wonderland, there are $$$N$$$ cities connected by roads. The road network has a special property — there is exactly one path between any two cities. A path is a sequence of different cities connected sequentially by roads.

The Queen of Wonderland maintains many teams of $$$K$$$ guards in her barracks. She wants to deploy one of these teams to protect all cities against potential threats within the kingdom. Each guard protects the city they are stationed in, as well as all cities whose distance from that city along the roads is at most $$$R$$$. The distance between two cities is defined as the number of roads on the unique path connecting them.

All guards in a single team have the same protection radius $$$R$$$. Since the Queen wants to keep her strongest guards in reserve, she wishes to choose a team and deploy it in such a way that every city is protected while minimizing the radius $$$R$$$.

Your task is to determine the minimum possible value of $$$R$$$ such that it is possible to place the $$$K$$$ guards in some cities so that every city in Wonderland is protected by at least one guard.

Shanto has finally decided that it's time for him to get married!

Although it took a while for him to reach this decision, it didn't take long for the news to spread like wildfire. Soon, Shanto's phone started to ring nonstop, with $$$n$$$ girls requesting to chat with him, each seeing him as a perfect life partner. Being overwhelmed, Shanto devised an algorithm to find his favorite girl.

Here's his plan:

• Tomorrow, Shanto will chat with the girls one by one in the order they called.
• For every girl, Shanto will calculate the happiness he feels during the chat.
• At any point, Shanto will keep track of the favorite girl he's met so far.
• After chatting with the first girl, she's automatically the favorite girl (for now).
• For subsequent girls:
  • If the happiness Shanto feels chatting with her is less than that of the current favorite girl, he will stick with his favorite girl.
  • If it's greater, she will become the new favorite girl.
  • If it's equal, Shanto will flip an unbiased coin. If the coin lands on heads, he will stick to his current favorite girl. Otherwise, this girl will become the new favorite girl.
• If Shanto can finish chatting with all the girls, he will choose his favorite girl to become his wife.
• However, at any point, if Shanto chats with $$$k$$$ consecutive girls and no girl strictly surpasses his maximum happiness, he'll cancel the rest of the dates and go to sleep. In this case, his current favorite girl gets to become "Mrs. Shanto"!

Being an honest boy, Shanto shares all the details about the algorithm with the girls. But here's a twist: Shanto himself doesn't know the value of $$$k$$$ yet. Influenced by one of his roommates, Shanto has developed a habit of making important decisions at the last moment. So, he decided to sleep on it and choose $$$k$$$ tomorrow morning.

Meanwhile, the girls, excited and anxious, started fantasizing about their chances. Some have tried to read Shanto's mind and guess the value of $$$k$$$. Others have decided to pray for an optimal $$$k$$$ to maximize their chances. Now, they've turned to you, the only person who can predict Shanto's happiness levels, for help.

Your task is to calm their nerves by answering their queries.

Kabul Kabir is a computer science student who decided to improve his health by taking a regular morning walk. He walks on a park trail that forms a closed, simple loop of total length $$$L$$$ meters. The trail has multiple entry points and walkers may move in either direction along the trail.

Kabul always walks in the forward direction at a constant speed of $$$v_0$$$ meters per second and continues walking for exactly $$$T$$$ seconds.

While walking, Kabul encounters other walkers on the trail. Some walk in the same direction, while others walk in the opposite direction. Whenever Kabul and another walker occupy the same position on the trail at the same time, Kabul considers it a meeting. Meetings can occur either when they cross paths (opposite directions) or when one overtakes the other (same direction).

For each walker $$$X_i$$$, Kabul records the following information:

• $$$t_i$$$ – the time (in seconds) after Kabul starts walking when he first meets $$$X_i$$$.
• $$$v_i$$$ – the signed walking speed of $$$X_i$$$ in meters per second: positive if the walker moves in the same direction as Kabul, and negative if the walker moves in the opposite direction.

Your task is to determine how many times in total Kabul meets each walker during the time interval from $$$0$$$ to $$$T$$$, including the first meeting and any meeting that occurs exactly at time $$$T$$$.

Alice has picked up a new logic puzzle called a nonogram. A nonogram is played on a board consisting of $$$n$$$ cells arranged in a row. You are given a sequence $$$b_1, b_2, \dots, b_k$$$. You must color each cell black ('1') or white ('0') such that the contiguous blocks of black cells have lengths exactly $$$b_1, b_2, \dots, b_k$$$.

For example, if $$$n = 6$$$ and the clue sequence is $$$[3, 1]$$$, the board must contain a block of $$$3$$$ black cells, followed by at least one white cell, followed by a block of one black cell. There can be any number of white cells before the first block, after the last block, or between blocks (as long as there is at least one). So valid solutions are 011101, 111001 or 111010.

Alice has become a master at solving nonograms and now finds them boring. To make things more interesting, her friend Bob introduces an additional constraint. He colors some of the cells white ('0'), and leaves the rest empty ('?'). Alice must solve the nonogram while ensuring every cell Bob colored remains white.

Help Alice figure out if it is possible to find a solution to the puzzle consistent with Bob's constraints. In other words, you need to determine if you can color each '?' cell black or white so that the contiguous blocks of black cells have lengths exactly $$$b_1, b_2, \dots, b_k$$$.

In addition, if it is solvable, then for each cell, you must find whether it is definitely black ('1'), definitely white ('0'), or can be either ('?').

You are given an array of positive integers $$$A$$$ of size $$$n$$$. In one operation, you may perform the following:

• Choose any indices $$$i, j$$$ such that $$$1 \le i, j \le n$$$,
• Choose a positive integer $$$p$$$ that divides $$$A_i$$$, formally, $$$p \mid A_i$$$,
• Update $$$A_i := \frac{A_i}{p}$$$,
• Update $$$A_j := A_j \cdot p$$$.

After performing the operation any number of times (possibly zero), the final array must satisfy the following requirements, one from each of your three friends:

• Muhaimin wants at least $$$a$$$ elements to be evenly even. A positive integer is called evenly even if it has no odd prime factor.
• Noshin wants at least $$$b$$$ elements to be oddly odd. A positive integer is called oddly odd if it has no even prime factor.
• Osman wants the whole array to be balanced. An array is called balanced if each element of the array is either evenly even, or oddly odd, or both. For example, [4, 27] is a balanced array, while [6, 9] is not.

Determine the minimum total cost required to satisfy all three requirements. It can be proved that it is always possible to satisfy all three requirements.

Pebae has a string $$$A$$$ and Mr Blue has a string $$$B$$$, both of length $$$N$$$ (1-indexed). For a string $$$S$$$, let $$$S[i \ldots j]$$$ denote the contiguous substring from index $$$i$$$ to $$$j$$$ (inclusive).

Now they want to find all the ways their strings can be attached! Specifically, count the number of pairs $$$(i, j)$$$ with $$$1 \leq i, j \leq N$$$ such that: $$$$$$A[1 \ldots i] + B[j \ldots n] = A[j \ldots n] + B[1 \ldots i]$$$$$$.

Here, $$$+$$$ denotes string concatenation. Please help them find the number of valid pairs.

You are analyzing a string literal written in the C programming language. In C, special characters inside string literals are represented using escape sequences, all of which begin with a backslash (\).

Some relevant escape sequences are:

• \\: represents a single backslash character \
• \ 0: represents the null character (NUL). In C, the function strlen stops counting characters when it encounters the first NUL.

You are given a string $$$S$$$, which represents the characters written inside the quotation marks of a C string literal. The string $$$S$$$ consists only of two characters: backslash (\) and zero (0).

Your task is to determine the value that the C function strlen would return after interpreting all escape sequences in $$$S$$$. If $$$S$$$ contains an incomplete escape sequence (i.e., a single backslash at the end of the string), then $$$S$$$ is considered INVALID, and you should report that instead.

The string $$$S$$$ is scanned from left to right according to the following rules:

• If the current character is 0 and it is not part of an escape sequence, it is treated as a normal character and contributes $$$1$$$ to the string length.
• If the current characters form the escape sequence \\, they produce a single backslash character and contribute $$$1$$$ to the string length.
• If the current characters form the escape sequence \ 0, they produce a NUL character. At this point, strlen stops immediately, and the NUL character is not counted.
• If any escape sequence is incomplete, and the string is considered INVALID.