A large music festival featuring many different genres took place in the city of Campinas, attracting visitors from all over the country. However, it is now two o'clock on Sunday morning, and the festival has come to an end. Still full of energy, several groups of visitors decided to look for an after-party to keep the night going.

Fortunately, they found a list of nightclubs open that night in the city, all of which offer an open bar. For each nightclub, the list provides the entrance fee and the predominant music genre.

Since the visitors are unfamiliar with the city, every group will follow the order of the list exactly to find the first nightclub they can attend. Each group has a maximum amount of money they are willing to spend per person and also rejects a particular music genre. Therefore, a group will choose the first nightclub on the list whose entrance fee does not exceed their budget and whose predominant music genre is not the one they reject.

Your task is to determine which nightclub will be chosen by each group of visitors.

Raphael occasionally uses the subway system in the city of São Paulo and is now going to start using a ticket with a new fare scheme: a time-valid pass. When purchasing this type of ticket, one may choose a duration of $$$D$$$ days, with a cost of $$$C$$$ reais per day, resulting in a total cost of $$$D \cdot C$$$. With this ticket, the subway can be used freely for $$$D$$$ consecutive days (the day of purchase and the following $$$D-1$$$ days).

However, Raphael must take a ride-hailing service to reach the ticket office where this new type of pass is sold. Although online purchasing methods are available, Raphael prefers to pay in cash and receive a physical ticket. This ride has a cost of $$$K$$$ reais. Therefore, in practice, the total cost for Raphael to purchase a pass valid for $$$D$$$ days is $$$D \cdot C + K$$$ reais.

Raphael already knows the list of $$$N$$$ days on which he will need to use the subway, and he has asked for your help in determining the minimum possible cost that allows him to use the subway on all those days by purchasing only time-valid passes. Initially, Raphael does not own any valid ticket.

For example, suppose that $$$C = 3$$$, $$$K = 10$$$, and Raphael needs to use the subway on three days: 2 days from now, 3 days from now, and 8 days from now. One possible strategy would be to buy, 2 days from now, a pass valid for 7 days, resulting in a cost of $$$7 \cdot 3 + 10 = 31$$$. However, he could instead buy a pass valid for 2 days, 2 days from now, and another pass valid for 1 day, 8 days from now, resulting in a total cost of $$$(2 \cdot 3 + 10) + (1 \cdot 3 + 10) = 29$$$, which is therefore a cheaper option.

São Paulo is widely celebrated as the Pizza Capital of the World. The city produces nearly 4 pizzas per second, surpassing the mark of 300,000 pizzas per day. It is the second-largest consumer of pizza in the world, behind only New York City.

In this problem, you must help calculate an essential piece of information when ordering pizza delivery. If there are $$$N$$$ pizzas, each cut into 8 slices, and $$$M$$$ people sharing them, what is the maximum number of slices each person can eat if everyone must eat the same number of slices?

For example, if there are 2 pizzas and 3 people, then there are 16 slices in total, and each person can eat at most 5 slices (leaving 1 slice uneaten).

ASCII art is a form of artistic expression that uses only the characters available in computer character encoding tables. Even before computers existed, a similar form of art was created using typewriters. In this task, you must draw the shape of the state of São Paulo following the examples provided. The drawing must be scaled proportionally according to a given integer $$$N$$$.

The Artemis VII Orbital Research Station consists of $$$N$$$ modules connected by $$$N-1$$$ pressurized corridors, in such a way that it is possible to travel from any module to any other by traversing the corridors. Each corridor has a length measured in meters.

Over time, engineers arrive at the station. Initially, no module contains any engineers, and a single module may host multiple engineers simultaneously. The total number of engineers in the station is always even.

In the event of an emergency, all engineers must gather into pairs. Each engineer must meet exactly one other engineer by traveling through the corridors, and every engineer must belong to exactly one pair. The cost of an emergency response is the minimum total distance that the engineers need to travel, summed over all pairs. In other words, it is the sum of the distances between the two engineers in each pair, minimized over all possible ways of forming the pairs.

You are given a sequence of $$$Q$$$ events. In each event, two new engineers arrive at the station and are assigned to modules $$$x$$$ and $$$y$$$ (not necessarily distinct). After each event, determine the cost of an emergency response considering all engineers currently present in the station.

One of the most popular internet slang expressions at the moment is "farming aura", which means accumulating style, charisma, respect, or presence points. The term combines the gaming expression "to farm" (repeating actions to accumulate points) with aura (a person's energy, vibe, or attitude). One of the online games where this slang became popular is Fibia, a game in which the objective is to explore a vast world represented as a two-dimensional map viewed from above.

In a certain game scenario, there are $$$N$$$ points and $$$M$$$ segments connecting pairs of these $$$N$$$ points. Each segment represents a wall in the game world. These segments do not intersect and may touch only at their endpoints, which are among the $$$N$$$ points (none of the $$$N$$$ points lies in the interior of any of the $$$M$$$ segments).

Depending on a player's position in this scenario, the player may become "trapped" by these segments; that is, the player's position lies inside a polygon bounded by the segments. When a player is in such a position, they are considered to be "losing aura", since they cannot explore the entire map unless they use some teleportation spell. Otherwise, the player is considered to be "gaining aura".

In the figure above, players at positions $$$A$$$ and $$$C$$$ are "gaining aura", while players at positions $$$B$$$ and $$$D$$$ are "losing aura".

Given the positions of $$$K$$$ players on the game map, your task is to determine which players are losing aura and which are gaining aura.

The city of Graphs of Jordan is being prepared for a major festival. To host the event, $$$N-1$$$ avenues are being built to connect $$$N$$$ different locations in the city. The avenues were chosen in such a way that there exists one and only one path between every pair of these $$$N$$$ locations using only those $$$N-1$$$ avenues.

To make the avenues more attractive for the festival, $$$M$$$ different colors were selected to paint some of them.

The painting process was carried out as follows: $$$M$$$ pairs of locations among the $$$N$$$ city locations were chosen. First, all avenues along the path between the first pair of locations were painted with color 1; then, all avenues along the path between the second pair were painted with color 2; and so on. Note that this process may overwrite the color of avenues that were painted previously. Whenever an avenue is painted again, its previous color is completely removed, and the avenue remains painted only with the new color. Initially, no avenue is painted, and after the painting process is completed, some avenues may still remain unpainted.

After the painting process, a closing parade is planned for the festival. The event organizers want to hold a parade starting at a location $$$A$$$ and ending at a location $$$B$$$ such that every avenue along the path from $$$A$$$ to $$$B$$$ is painted and all of them have the same color. They need your help to determine the longest possible route that can be used for this parade.

In addition, there is a list of $$$Q$$$ events that may affect the choice of the parade route.

For a parade to be held between two locations $$$A$$$ and $$$B$$$, besides the requirement that all avenues on the path have the same color, no intermediate location on the path between $$$A$$$ and $$$B$$$ may be blocked in a way that prevents the parade from passing through it. Initially, all $$$N$$$ locations in the city are unblocked and available for the parade.

However, there is a sequence of $$$Q$$$ events in which a certain location $$$P_i$$$ becomes blocked or unblocked. After each event in this sequence, your program must also determine the length of the new longest possible route that can be used for the parade.

Reinaldo is a driver who works in the city of São Paulo, starting his demanding routine every day at 5:00 AM. He must visit $$$N$$$ different locations in order to complete his work. Despite São Paulo's traffic, Reinaldo always takes the same amount of time: $$$T_1$$$ minutes to travel from his home to the first location, $$$T_2$$$ minutes to travel from the first location to the second, and so on.

The problem is that on one day of the week, the city of São Paulo enforces a vehicle restriction system based on license plate numbers. Under this system, Reinaldo is not allowed to drive between 7:00 AM and 10:00 AM, nor between 5:00 PM and 8:00 PM. Whenever one of these restricted periods begins while Reinaldo is driving, he must stop his car wherever he is and resume driving only after the restriction period ends.

Can you help Reinaldo determine how long it will take him to complete his work routine on a day when the license plate restriction is in effect?

At a Poupatempo service center in São Paulo, there is a self-service kiosk that, among many other pieces of information, requires users to enter their mobile phone number. Unfortunately, the system does not verify whether the entered phone number is valid, so users may enter any sequence of 1 to 20 digits, and the system will accept and store it.

To make matters worse, Poupatempo employees noticed that the digit keys most commonly used when entering mobile phone numbers, namely 1 and 9, have started to malfunction. When a user presses 1 or 9, there is a chance that the key press is not registered, causing the number to be saved without that digit.

Poupatempo has hired you to develop a program that, given a phone number stored for a user, prints all possible valid mobile phone numbers from the state of São Paulo that the user may originally have entered, considering that the 1 and 9 keys may have failed while the user was using the kiosk.

A mobile phone number from the state of São Paulo is considered valid if it consists of 11 digits, starting with two digits representing one of São Paulo's valid area codes (DDDs), followed by the digit 9, and then followed by any 8 additional digits.

The list of valid São Paulo area codes is:

• 11: São Paulo (capital), Greater São Paulo (Guarulhos, Osasco, ABC Paulista, etc.), and the regions of Jundiaí and Mogi das Cruzes.
• 12: Vale do Paraíba, São José dos Campos, Taubaté, Guaratinguetá, and the northern coast.
• 13: Baixada Santista, Santos, São Vicente, Guarujá, Praia Grande, and the southern coast.
• 14: Bauru, Marília, Botucatu, Ourinhos, and Jaú.
• 15: Sorocaba, Itapetininga, and surrounding areas.
• 16: Ribeirão Preto, Franca, Araraquara, and São Carlos.
• 17: São José do Rio Preto, Catanduva, and Votuporanga.
• 18: Presidente Prudente, Assis, Dracena, and Araçatuba.
• 19: Campinas, Piracicaba, Limeira, Americana, and Rio Claro.

For example, if the stored number is 11983609574, then the only valid number the user could have entered is the stored number itself. However, if the stored number is 1922222222, then there are two valid phone numbers that the user could originally have entered: either 19922222222, if the third digit failed to register, or 11922222222, if the second digit failed to register.

Ana and Beto created a game using intervals of integers. The game starts with an interval from $$$A$$$ to $$$B$$$ ($$$A \lt B$$$). On each move, the current player must choose either to increase the value of $$$A$$$ by one or decrease the value of $$$B$$$ by one. Ana makes the first move, Beto makes the second, Ana the third, and so on, alternating turns.

There are also $$$N$$$ special intervals of integers that influence the game. Beto's goal is to score as many points as possible by making the current interval $$$[A, B]$$$ become equal to one of these $$$N$$$ special intervals immediately after his move. In that case, the game ends and Beto earns a number of points equal to the size of the interval, that is, $$$B - A$$$ points.

On the other hand, Ana's goal is to minimize the number of points Beto earns. If at any point, after either player's move, the values of $$$A$$$ and $$$B$$$ become equal, the game ends and Beto earns 0 points.

Note that if $$$[A, B]$$$ becomes equal to one of the special intervals after Ana's move, or if the initial interval is already equal to a special interval, the game does not end and play continues normally.

For example, suppose the only special interval is $$$[1,2]$$$ and the game starts with $$$[A,B]=[0,3]$$$. On her first move, Ana may transform the interval into either $$$[1,3]$$$ or $$$[0,2]$$$. In both cases, Beto can then make the interval equal to $$$[1,2]$$$ on his next move and earn 1 point.

If the initial interval is $$$[0,2]$$$, $$$[1,3]$$$, or $$$[1,2]$$$, then in all of these cases the game ends with Beto earning 0 points.

Assuming Ana and Beto both play optimally, they would like your help answering the following question: given a positive integer $$$K$$$, if an initial interval $$$[A,B]$$$ is chosen uniformly at random among all intervals satisfying $$$0 \leq A \lt B \leq K$$$, what is the expected number of points Beto earns?

In other words, compute the arithmetic mean of the outcomes over all possible initial intervals.

Marquinhos Carlsen is a great enthusiast of the game of chess. Although chess is played on an $$$8 \times 8$$$ board, Marquinhos enjoys performing mathematical analyses by imagining an infinite chessboard placed on a Cartesian plane. His favorite chess piece is the knight (knight in English), because it has a very interesting movement pattern. On an infinite board, a knight always has $$$8$$$ possible "L"-shaped moves: on each move, the knight must move $$$2$$$ squares in one direction and $$$1$$$ square in a perpendicular direction.

In the figure below, a knight at position $$$(2,2)$$$ can move to positions $$$(1,4)$$$, $$$(3,4)$$$, $$$(0,3)$$$, $$$(4,3)$$$, $$$(0,1)$$$, $$$(4,1)$$$, $$$(1,0)$$$, and $$$(3,0)$$$. Squares are represented by their lower-left corner coordinates in the Cartesian plane.

In one of his mathematical analyses, Marquinhos placed $$$N$$$ knights on this infinite board and defined the "knight distance" of every board position as the minimum number of moves required for at least one of the knights to reach that position.

Using this, he also defined the "knight number" of every position, which is a unique positive integer assigned according to the following ordering of all positions on the board: first, positions are ordered by increasing knight distance; ties are broken by decreasing vertical coordinate; and any remaining ties are broken by increasing horizontal coordinate.

In the figure below, two knights are placed at positions $$$(2,2)$$$ and $$$(5,3)$$$. Each visible position is labeled with its "knight number". Note that there are infinitely many positions outside the figure that are not shown, including positions with negative coordinates.

Marquinhos wants your help analyzing the "knight number". He has a list of $$$Q$$$ positive integers and wants to know, for each of them, which position on the infinite chessboard has the corresponding knight number.

The organizers of the São Paulo Programming Contest decided to create a special system to control the entry of teams into the competition area. There are $$$N$$$ teams registered for the contest, each with a unique identifier between $$$0$$$ and $$$N - 1$$$.

To organize the flow of participants, a network of checkpoints is built. Each checkpoint has a distinct number $$$v$$$ between $$$0$$$ and $$$N - 1$$$ and may have a corridor to the left and/or a corridor to the right, thus having $$$0$$$, $$$1$$$, or $$$2$$$ corridors in total.

The checkpoint structure must satisfy the following property: for every checkpoint numbered $$$v$$$, all checkpoints reachable through its left corridor have numbers smaller than $$$v$$$, while all checkpoints reachable through its right corridor have numbers greater than $$$v$$$.

The goal of each team is to reach the checkpoint whose number matches its identifier. When a team arrives at a checkpoint numbered $$$v$$$, its identifier $$$id$$$ is compared with $$$v$$$:

• if $$$id \lt v$$$, the team proceeds through the left corridor;
• if $$$id \gt v$$$, the team proceeds through the right corridor;
• if $$$id = v$$$, the team remains at that checkpoint.

Each corridor leads to another checkpoint, where the same process is repeated. Thus, a team may pass through several checkpoints before reaching its final destination.

During the day, the teams arrive in the order specified by a sequence $$$P$$$. To analyze the efficiency of a particular checkpoint $$$u$$$, only the teams that pass through it without remaining there are considered. For each such team:

• record E if it is sent through the left corridor of $$$u$$$;
• record D if it is sent through the right corridor of $$$u$$$.

This produces a sequence $$$S$$$ consisting of the characters E and D. The contribution of a checkpoint is the number of adjacent pairs of positions whose characters are different. In other words, the number of positions $$$i$$$ such that $$$S_i \neq S_{i+1}$$$.

The total score of the system is the sum of the contributions of all checkpoints.

Rouse knows the sequence $$$P$$$ and wants to determine the maximum possible total score that can be achieved by choosing the best possible checkpoint structure. Can you help her?

During a long bus trip through São Paulo, Miguel likes to observe street signs through the window. The route seems endless: the bus crosses long avenues such as Avenida Sapopemba, Avenida Aricanduva, and Avenida Raimundo Pereira de Magalhães, while Miguel tries to distract himself with the names that appear along the way.

At one point during the trip, as he passes through a region of the city, he sees the same sequence of letters $$$s$$$ repeated $$$p$$$ times. Later, after many stops, he sees the sequence $$$t$$$ repeated $$$q$$$ times.

On the way back home, however, the route is different: first appear the signs with $$$t$$$ repeated $$$q$$$ times, and only afterwards the signs with $$$s$$$ repeated $$$p$$$ times. Miguel decides to mentally compare the two huge letter sequences using lexicographic order, but they are too large to be written out completely.

Given a string $$$u$$$ and a non-negative integer $$$k$$$, let $$$u^k$$$ be the string formed by concatenating $$$k$$$ copies of $$$u$$$. In particular, $$$u^0$$$ is the empty string.

Recall that, in lexicographic order, a string $$$a$$$ is smaller than a string $$$b$$$ if, at the first position where they differ, the character of $$$a$$$ is smaller than the character of $$$b$$$. If one of the strings ends before any difference is found, then the shorter string is considered smaller.

Your task is to compare lexicographically the strings $$$s^p t^q$$$ and $$$t^q s^p$$$.

A research laboratory has developed the mysterious Compound S, an unstable substance capable of altering the structure of biological samples. The laboratory has an original batch $$$A$$$ containing $$$N$$$ samples, each with a reactivity level represented by a non-negative integer.

Before the experiment, the scientists recorded two crucial safety metrics:

• $$$S$$$: The total reactivity of the batch (the sum of the reactivity levels of all samples in $$$A$$$).
• $$$M$$$: The maximum reactivity level present in a single sample of $$$A$$$.

During the experiment, the entire batch was exposed to Compound S. The chain reaction caused each sample to mutate: its new reactivity level became the sum of the reactivity levels of all the other samples in the original batch.

To stabilize the reaction, the scientists injected two control samples into the batch, having reactivity levels exactly equal to the global values $$$S$$$ and $$$M$$$. Due to the volatility of the process, the resulting $$$N+2$$$ samples were completely mixed, forming the chaotic batch $$$B$$$.

Your task is, given the mixed batch $$$B$$$, to determine the original values $$$S$$$ and $$$M$$$, and reconstruct the reactivity levels of the original batch $$$A$$$, printing them in non-decreasing order.