Mariana Counts $$$1$$$ is a song often used while children are learning to count, since it presents counting in a didactic and playful way. For older children, the song was generalized into Mariana Counts $$$X$$$ (where $$$X$$$ is a natural number), and goes as follows:

To measure its didactic value, print how many numbers appear in the song.

Because of its fun mechanics, Super Bario World is a hit among gamers from Minas Gerais. In the game, Bario moves through levels made of $$$N$$$ blocks, each of which may be either a solid block or a hole. The goal is to get from the start of the level (block $$$1$$$) to the end (block $$$N$$$) without falling into any hole. Bario can run over solid blocks and, to avoid holes, he can jump over them.

Bario wears boots with an energy charge, initially equal to $$$1$$$. While running, he charges the boots so he can jump farther – each solid block Bario runs over adds one unit of charge to his equipment. A jump with charge $$$v$$$ lets Bario go from block $$$b$$$ to any block from $$$b+1$$$ to $$$b+v$$$; after landing, the boots lose their energy and return to their initial charge of $$$1$$$.

Compute the minimum number of jumps Bario needs to reach position $$$N$$$, or report that it is impossible.

One day, Rened decided to invite his friends to play a card game. The game consists of a sequence of numbered cards on a table, initially empty. The players take turns adding new cards to the end of this sequence; the $$$i$$$-th player plays the card with value $$$C_i$$$.

The main rule is simple: there cannot be cards with repeated numbers on the table.

Whenever a player plays a card whose number does not appear in the current sequence, it is simply added to the end, extending the sequence normally.

However, if a player plays a card with the same value as another card already on the table, an elimination occurs: all cards from the beginning of the current sequence up to and including the previous card with this value are removed. Then, the newly played card is placed at the end of the sequence. Notice that after this process no repeated values remain on the table, and the sequence is never empty.

To make the game faster, Rened asked you and your team to develop a system that tracks the state of the game and, after each play, reports the largest-value card still on the table and the index of the player who played it.

NeoSpace is an innovative startup that uses advanced Artificial Intelligence models to process massive volumes of corporate information. In the company's hallways, engineers often tell a classic joke: despite being experts at handling Big Data, the system's greatest nightmare is still the small dates entered incorrectly by users.

Recently, the platform started integrating data from new international clients. During data ingestion, the team noticed a serious problem in the interface: while the system expects the Brazilian Day/Month (DD/MM) format, many foreign users fill out the forms in the Month/Day (MM/DD) format.

To ensure the quality of the AI model, the pipeline must identify when an entry may cause confusion. For example, the value 1/6 is problematic, since it may be interpreted as June 1st or January 6th. The value 28/2, on the other hand, is safe, since there is no month 28 in the calendar. Also, a value such as 9/9 is safe: both interpretations refer to the same date.

Your task is to create an algorithm that analyzes the input provided by the user and determines whether the given numbers can lead to this double interpretation.

Giovana and Arthur have just been hired by ArcelorMittal Sistemas to develop cutting-edge technology for mineral extraction. As their first project, both implemented algorithms and heuristics to create an exploration plan for a drilling machine, a machine commonly used in mines, with the goal of maximizing the ore extracted after $$$T$$$ minutes of operation. The mine where Giovana and Arthur are working is represented by an $$$N \times M$$$ matrix, where each cell contains the value obtained if that position is drilled by the machine. Each exploration plan consists of $$$T$$$ pairs of coordinates $$$(i_1, j_1), \ldots, (i_T, j_T)$$$, where $$$(i_t, j_t)$$$ is the row and column where the drilling machine will be at time $$$t$$$.

Very pleased with the projections of Giovana's and Arthur's algorithms, the company's directors decided that both exploration plans will be executed simultaneously, each with its own drilling machine. The problem is that Giovana's and Arthur's exploration plans were not designed with the presence of the other drilling machine in mind, which could cause conflicts during ore extraction!

Fortunately, the control software developed by ArcelorMittal Sistemas is quite sophisticated and can handle this kind of situation! Besides the mechanical control of the drilling machines, it establishes a communication network between the pieces of equipment, preventing the machines from exploring the same position simultaneously. Thus, when a drilling machine is at position $$$(i,j)$$$, it can extract ore from cell $$$(i,j)$$$ and from cells $$$(i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)$$$, but it does so only if the other drilling machine would not extract that same cell at that same time. Extraction is 100% efficient: after its ore has been extracted, a cell has zero units of ore. In the example in the figure below, if at time $$$t$$$ Giovana's drilling machine is at position $$$(1, 1)$$$ and Arthur's is at position $$$(1, 3)$$$, neither drilling machine will extract ore from cell $$$(1, 2)$$$, leaving all the ore that was there intact. On the other hand, all other cells of interest to each drilling machine will have their ore extracted.

Visual representation of Example 1. On the left, the matrix with the amounts of ore in each cell. In the center, the cells explored by each drilling machine at time $$$t = 1$$$: red squares are cells explored by Giovana, and blue diamonds are cells explored by Arthur. On the right, the cells explored by each drilling machine at time $$$t = 2$$$;

Curious to know how their plans will fare, Giovana and Arthur asked for your help. Write a program that, given the matrix representing the mine and the exploration plans of each of them, prints the total ore extracted by each drilling machine. It is guaranteed that both exploration plans have the same duration $$$T$$$.

Among the many delicacies of Minas Gerais, cheese and doce de leite are the most famous. Although both are made from the same raw material, milk, their production and storage processes are quite different. In particular, all the cheese in the state is produced in city $$$A_1$$$ and stored in city $$$A_2$$$, while all the doce de leite is produced in city $$$B_1$$$ and stored in city $$$B_2$$$. To move the stocks from one city to another, each product is transported along some of the $$$M$$$ two-way roads, each of which connects exactly two of the $$$N$$$ cities in Minas Gerais.

Besides their culinary importance, cheese and doce de leite are fundamental to the state's political and social stability: a shortage of both delicacies, even for a short time, is enough to turn our characteristic hospitality into deep animosity. Concerned about this possibility, the Movement of Minas Pacifists (MMP) needs to know: what is the minimum number of roads that, if closed, would make it impossible to transport the cheese from $$$A_1$$$ to $$$A_2$$$ and the doce de leite from $$$B_1$$$ to $$$B_2$$$? Write a program to help the MMP find this answer.

In the figure above, there are four shirts, using seven clothespins, forming three groups of shirts.

To hang a shirt on the clothesline, we must use two clothespins (one at each end of the shirt). On the other hand, with two shirts, we can use only three clothespins by fastening the ends of two consecutive shirts with the same clothespin. When this happens, we say that a group of shirts has been formed, and that the shirts fastened by the same clothespin belong to the same group. Being in a group is a transitive property: if shirt A belongs to the same group as shirt B, and shirt B belongs to the same group as shirt C, then shirts A and C also belong to the same group. A shirt that does not share a clothespin with any other shirt forms a group by itself.

Dilson wants to hang $$$N$$$ shirts on the clothesline and, at the same time, wants exactly $$$G$$$ groups of shirts to be formed. What is the minimum number of clothespins Dilson needs to use to achieve his goal?

The Maratona Mineira team is organizing a treasure hunt. The treasure will be two chests of the most delicious doce de leite in the world, a cultural heritage of Minas Gerais, which will be hidden on the game map.

The map consists of $$$N$$$ vertices, numbered from $$$1$$$ to $$$N$$$, and $$$N - 1$$$ edges, in such a way that it is possible to go from any vertex to any other. In other words, the map forms a tree. The distance between two vertices is defined as the number of edges in the unique simple path between them.

The team already has the map, but still needs to choose in which vertices to hide the two chests. A choice is considered valid if the chests are placed on distinct vertices and the number of vertices closer to the first chest is equal to the number of vertices closer to the second chest. Vertices at the same distance from both chests do not count towards either one.

The figure above shows a valid choice for Example 1. The chests were placed at vertices $$$1$$$ and $$$7$$$. Thus, vertices $$$1$$$, $$$2$$$, and $$$3$$$ (red circles) are closer to the chest at vertex $$$1$$$, while vertices $$$5$$$, $$$6$$$, and $$$7$$$ (blue diamonds) are closer to the chest at vertex $$$7$$$. Vertex $$$4$$$ (yellow star) is at the same distance from both chests.

Determine the number of valid ways to choose the positions of the chests. Two ways are considered distinct if the set of vertices where a chest was placed is different.

A great meeting among diplomats from $$$N$$$ peoples will be held to discuss the future of the continent. The event has a total of $$$M$$$ cataloged languages. The problem is that not all diplomats share a common language. For a message to get from one point to another, it may be necessary to use other diplomats as intermediaries.

However, every time the message must be translated from one language to another (when an intermediary hears it in one language and speaks it in another), a language switch occurs. To minimize misunderstandings, the conclave organizers need to find the minimum number of switches required for two diplomats to communicate.

Given the sets of languages spoken by each of the $$$N$$$ diplomats and $$$Q$$$ queries $$$(a, b)$$$, determine the minimum number of language switches needed for diplomats $$$a$$$ and $$$b$$$ to communicate. If communication is impossible, print $$$-1$$$.

A group of $$$N$$$ friends is going to play a game in which each player chooses an integer $$$P_i$$$. Then an integer $$$X$$$ greater than 1 was supposed to be drawn, but Pedro found a way to cheat and can choose this value.

Each player's score is given by $$$P_i \bmod X$$$, that is, the remainder of the division of $$$P_i$$$ by $$$X$$$.

Any player whose score is equal to $$$0$$$ is called a beta, because nothing is left from the division.

Help Pedro choose a value of $$$X$$$ that maximizes the number of beta players.

The University of the Minas Heptagon is creating a new operating system, "Janelas OS", which will come installed with the famous game Minesweeper. To avoid legal trouble, they decided to make 1-D Minesweeper, a version different enough to calm down the competitors' lawyers. The game works as follows:

• The minefield has $$$N$$$ positions, and each position may be empty or contain a mine.
• Each position may be revealed or secret – initially, all positions are secret.
• In each round, the player chooses a secret position and clicks it:
  • If the position contains a mine, the player loses.
  • If the position is empty, that position and all positions to the left and to the right of the click are revealed until the end of the field is reached or a mine is reached (that mine is also revealed).
• If at any moment all empty positions are revealed, the player wins. This may happen before the first click if there are no empty positions.

In the figure above, there are two example games for a given minefield. The one on the left ends in victory because all empty positions are found, and the one on the right ends in defeat because the player clicks a mine.

To help the university understand how long the game can entertain its users, given $$$N$$$, print how many different games can be played on a field of size $$$N$$$. Two games are considered different if the minefield is different, or if any move differs in order or position. Since the number of games can be very large, print the answer modulo $$$P$$$ – that is, the remainder of the division by $$$P$$$.

After an excellent family breakfast with cheese bread, Beto was put in charge of washing the dishes. After soaping everything, Beto remembered how annoying it is to put the cups in his home's linear dish rack, especially the work needed to place a cup between two others that are already drying. He estimated that the effort to place a cup in a given position of the dish rack is equal to the sum of the number of consecutive cups immediately to the left and the number of consecutive cups immediately to the right of that position at the time of placement.

In the figure above, we have the final state of a solution for Example $$$1$$$ – $$$4$$$ cups in a dish rack with $$$6$$$ positions.

Given the size $$$N$$$ of the dish rack and the number $$$C$$$ of cups, compute the minimum total effort Beto must spend to place all cups in the dish rack and provide an insertion sequence that achieves this minimum effort. The dish rack positions are numbered from $$$1$$$ to $$$N$$$, and each cup must be placed in an empty position. If there is more than one way to achieve the minimum effort, print any of them.

The renowned creators of pick-up sticks have just released the sliding-sticks puzzle. The puzzle consists of $$$N-1$$$ sticks connected to $$$N$$$ pins placed in the plane in convex position, forming a planar tree, that is, a connected and acyclic structure with no crossings.

The puzzle comes assembled in an initial configuration $$$T$$$, and the goal is to transform it into the final configuration $$$T'$$$ illustrated on the game box.

However, there is an important mechanical limitation: a stick cannot be moved freely. The only valid move is called a slide and works as follows:

• Consider two sticks $$$ab$$$ and $$$bc$$$. It is allowed to detach the common endpoint at $$$b$$$ of stick $$$ab$$$ and move it along stick $$$bc$$$, until connecting it to $$$c$$$.
• At the end of the move, no two sticks are allowed to cross.

Example: sliding edge $$$12$$$ along edge $$$32$$$.

We say that two sticks cross if their segments have a point in common that is not a shared endpoint; see the explanation of the second example below.

Since you have a dinner coming up and are short on time, you decided to add an extra restriction: your goal is to find a sequence of at most $$$2N$$$ slides that transforms $$$T$$$ into $$$T'$$$.

The $$$n$$$-checkers board is an $$$n \times n$$$ board with squares alternating between white and black, with the square in the top-left corner being white. A square may be empty or, if it is black, contain a piece.

On their turn, a player must choose one of their pieces to move. The chosen piece may capture an opponent's piece if that piece is on a diagonally adjacent square and the next square in the same diagonal direction is empty. In this case, the chosen piece "jumps" over the opponent's piece, moves to the immediately following empty square, and removes the opponent's piece from the board. After a capture, the player may continue the move with the same chosen piece.

In the official rules of $$$n$$$-checkers, there is a majority-capture rule: if on their turn a player has the opportunity to capture opponent pieces, they must perform a sequence of moves that results in the largest possible number of captured pieces.

During the final of the Minas Gerais $$$n$$$-checkers Tournament, a dispute arose between the finalists. Alice, playing with the black pieces, accused Bob, playing with the white pieces, of having made an illegal move. Bob claims he captured as much as he could, but Alice says there was a longer path. Write a program that determines the maximum number of pieces Bob can capture in one move sequence.

During mathematics class, the students in the back row made a huge ruckus. Annoyed by the situation, the teacher did not let it slide and decided to assign a challenging task as punishment.

The task consists of a list, initially empty, of mathematical operations containing addition and multiplication. There are also $$$N$$$ instructions. Each instruction has one of the following formats:

• + $$$x$$$: Append an addition by $$$x$$$ to the end of the list of operations.
• * $$$y$$$: Append a multiplication by $$$y$$$ to the end of the list of operations.
• ? $$$z$$$: Starting from value $$$z$$$, apply the list of operations in order, and output the result modulo $$$10^{9} + 7$$$ – the remainder of the integer division by $$$10^{9} + 7$$$.

Given the list of instructions, help the students with the assigned task.