You have been hired by a Brazilian HFT (High Frequency Trading) company, which uses robots to buy and sell stocks on the stock exchange in fractions of a second in a fully systematic and automated way. Your first task is to implement a signal: a number, computed from the current state of the market, that guides the robot's decision between buying, selling, or doing nothing. The signal you will compute determines whether, at that moment, there is more buying demand or more selling supply for a stock.

On the exchange, whoever wants to buy or sell stocks registers an order in the order book. The book consists of two queues: buy orders and sell orders. Orders are grouped into price levels, ordered from best to worst. For each level $$$i$$$, you are given $$$c_i$$$ (total shares in buy orders) and $$$v_i$$$ (total shares in sell orders).

The signal measures the book's imbalance for the first $$$n$$$ levels: $$$$$$ I_n = \frac{C_n - V_n}{C_n + V_n}, \qquad \text{where } C_n = \sum_{i=1}^{n} c_i \text{ and } V_n = \sum_{i=1}^{n} v_i. $$$$$$

The value of $$$I_n$$$ always lies between $$$-1$$$ and $$$1$$$ and is interpreted as follows:

• if $$$I_n \gt 0$$$, the signal indicates COMPRA;
• if $$$I_n \lt 0$$$, the signal indicates VENDA;
• if $$$I_n = 0$$$, the signal indicates NEUTRO.

Given the order book and a series of queries, where the $$$j$$$-th query has depth $$$n_j$$$, report the signal corresponding to each query.

You are given $$$N$$$ integer intervals $$$[L_i, R_i]$$$, in a fixed order. For each index $$$i$$$, exactly one integer $$$x_i$$$ belonging to the $$$i$$$-th interval must be chosen, that is, $$$L_i \leq x_i \leq R_i$$$.

A choice is valid if the sequence $$$x_1, x_2, \dots, x_N$$$ is strictly increasing, that is, if $$$x_1 \lt x_2 \lt \dots \lt x_N$$$. Two choices are considered distinct if they differ in at least one value $$$x_i$$$.

Compute the number of valid choices, modulo $$$10^9 + 7$$$.

Robertinho has been considering buying another keyboard, one of his favorite objects. Since he is going to travel abroad and knows that some products can cost much less outside the country, he wants help deciding whether it is worth buying the new keyboard there.

In Brazil, where he lives, the keyboard costs $$$C$$$ reais, the local currency. In Nlogônia, the country he will visit, the same keyboard costs $$$K$$$ nlogarian dollars. Given that the exchange rate is $$$T$$$ reais per nlogarian dollar, after conversion, the cost of the purchase abroad is equivalent to $$$K \times T$$$ reais.

Given the information about the current exchange rate $$$T$$$, the cost in Brazil $$$C$$$, and the cost abroad $$$K$$$, determine the smallest amount (in reais) that Robertinho can pay for the product.

The dragon keepers of Dragonland are reorganizing a large rectangular plot of land, divided into square cells of the same size, arranged in $$$N$$$ rows and $$$M$$$ columns. Some cells contain obstacles, such as mountains and lava pits, while the remaining cells are free spaces, each inhabited by a dragon.

To give the environment a fresh look without disrupting the group's dynamics, the keepers drew the current position of all the dragons on a transparent magic scroll, so that each free cell of the land corresponds to a mark on the scroll. They plan to relocate the dragons using this same scroll as a template. To do this, the keepers may freely manipulate the scroll on the table: they can rotate it in any direction or even flip it over (looking through the back of the transparent sheet).

A new arrangement is considered valid if the scroll aligns perfectly with the original boundaries of the land and if all the dragon marks fall exactly on free cells. Obviously, no dragon can be placed on an obstacle.

Your task is to compute the total number of valid ways to align the scroll to the land. Each distinct physical orientation of the scroll is counted as a different way, even if two orientations make the marks fall on exactly the same cells. The initial orientation, with the scroll neither rotated nor flipped, already counts as one valid way.

The company Sistemas Brasileiros de Conectividade (SBC) manages a network formed by $$$N$$$ stations, numbered from $$$1$$$ to $$$N$$$. Each connection in the network is a dedicated link formed by two terminals, one at each connected station. Connections are bidirectional, and there is at most one connection between each pair of distinct stations.

To modernize its infrastructure, SBC has prepared a desired configuration for the network. For cost reasons, during the reconfiguration the company neither buys nor discards terminals, but reuses the existing links. Furthermore, its field team is small and can only relocate one terminal per intervention.

In each intervention, the team chooses a connection between two stations $$$u$$$ and $$$v$$$, keeps one of the terminals at station $$$v$$$, and moves the other terminal from station $$$u$$$ to a station $$$w$$$. As a result, the connection between $$$u$$$ and $$$v$$$ is removed and a connection between $$$v$$$ and $$$w$$$ is installed. Stations $$$u$$$, $$$v$$$, and $$$w$$$ must be distinct, and the connection between $$$v$$$ and $$$w$$$ must not exist before the intervention.

Given the current and desired configurations of the network, determine the minimum number of interventions needed to transform the first into the second, or report that this transformation is impossible.

In the serene waters of the Amazon, riverside legends tell of a magical Victoria water lily. Unlike ordinary flowers, this one reacts to offerings. When seeds are placed in its center, the flower gently closes its petals and dives into the river. Moments later, it resurfaces and blooms, returning a strictly greater quantity of seeds.

This flower's magic does not act at random; it applies a deterministic, unchanging rule to compute the return. The flower keeps no memory of previous offerings: the amount returned depends only on the quantity of seeds deposited in that particular offering. The sages of the forest guarantee that the transformation obeys the following natural laws, which together guarantee a single possible outcome for each offering:

• The Law of the Whole Seed: The flower operates exclusively with integer quantities of seeds.
• The Justice of the Waters: Strictly larger offerings always result in strictly larger returns.
• Moapy: In the language of the ancients, the word means "three". It describes the flower's supreme secret. If you take all the seeds returned by an initial offering and deposit them into the flower again, the final amount returned will be exactly three times that initial offering.

On your journey, you found the rare Victoria water lily and deposited exactly $$$N$$$ seeds into it. The flower closed, sank, and bloomed exactly once (not twice!). However, the snap of a branch in the woods startled you, causing you to quickly stash the return in your pocket without having time to count it. Knowing the exact amount you offered at the start, you need to figure out how many seeds you now have with you.

A DNA sequence is represented by a string $$$T$$$. Several genes are also known, represented by strings and ordered from most relevant to least relevant. The genes are numbered sequentially, starting from 1.

$$$Q$$$ queries are made. Each one delimits a segment of $$$T$$$, between indices $$$L_i$$$ and $$$R_i$$$, inclusive. For each query, the goal is to determine the index of the most relevant gene that occurs entirely as a substring of that segment.

A street has $$$N$$$ traffic lights, numbered from $$$1$$$ to $$$N$$$. Each traffic light can be in one of two states: closed, represented by $$$1$$$, or open, represented by $$$0$$$.

To prepare the street for a special operation, $$$M$$$ control devices have been installed. Each device acts on a contiguous stretch of the street: when activated, it toggles the state of every traffic light within its range. Thus, closed traffic lights are opened, and open traffic lights are closed.

The $$$i$$$-th device affects the traffic lights whose indices are between $$$L_i$$$ and $$$R_i$$$, inclusive. Each device can be activated as many times as needed.

Is it possible to activate the devices so that all traffic lights end up open?

Jaime, a friendly guinea pig, and their clever friend Churro, also a guinea pig, have won the International Cavy Programming Contest. To celebrate their victory, they are organizing a party. They have $$$F$$$ other friends, numbered from $$$1$$$ to $$$F$$$, and sent invitations to $$$N$$$ of them (due to some budget limitations). Each invitation may cover several guests, such as the invited friend's family.

Each invited friend either accepted the invitation and specified their group's schedule, declined the invitation, or gave a tentative response that depends on whether another friend attends.

If a tentative response depends on a friend who declined, on a friend who was not invited, or on a circular chain of tentative responses, that friend will not attend.

Jaime and Churro will prepare a party playpen for the invited groups. At the minute when a group leaves, it no longer occupies the playpen, so its space can be used by groups arriving at that same minute. Determine the minimum guest capacity required for the playpen to accommodate all attending groups, excluding Jaime and Churro.

Phone companies have recently changed the way they operate. Since you and your two teammates need to train together for online programming marathons, you want to calculate how much you will spend to contact them by phone.

There are $$$N$$$ phone companies in total, numbered from 1 to $$$N$$$. Each company $$$U$$$ may have multiple directed communication lines. Each such line starts at company $$$U$$$ and reaches every company in an interval $$$[L, R]$$$. The communication cost varies as follows: the cost to connect company $$$U$$$ to company $$$L$$$ is $$$X$$$, to company $$$L+1$$$ is $$$X + K$$$, to company $$$L+2$$$ is $$$X + 2 \times K$$$, and so on, up to company $$$R$$$, for which the cost is $$$X + (R - L) \times K$$$. More formally, the cost to connect company $$$U$$$ to company $$$i$$$ ($$$L \leq i \leq R$$$) is $$$X + (i - L) \times K$$$.

The cost of a path is the sum of the costs of the connections that form it. The cost of a phone call from a company $$$U$$$ to another company $$$V$$$ is the smallest cost among all paths from company $$$U$$$ to company $$$V$$$. A path may use no communication line at all; therefore, the cost of a call from a company to itself is $$$0$$$.

You use the services of company 1, while your two teammates use the services of companies $$$A$$$ and $$$B$$$. You need to calculate the minimum total cost to call both of your teammates, that is, the sum of the minimum costs of the calls from company 1 to companies $$$A$$$ and $$$B$$$. You can only train together if it is possible to call both teammates.

A large automaker located in the Manaus Industrial Pole (PIM) manages a vast warehouse with $$$N$$$ different types of electronic components. The primary parts-picking system is efficient, with autonomous robots that fetch the needed components from the warehouse, based on optical sensors that identify the part type, and carry them to the main sorting conveyor, where they are sorted and sent to the assembly line.

Unfortunately, sensor failures can occur. In such situations, the factory relies on a contingency protocol: emergency robots remove components from the warehouse one at a time, but completely "blindly", without identifying which type of component they are picking up until it reaches the main sorting conveyor. As a result, in some situations, the robots may remove more units of certain components than necessary.

The factory has production targets that require $$$K_i$$$ units of component type $$$i$$$. Currently, the stock available in the warehouse has $$$C_i$$$ units of component $$$i$$$.

The logistics manager needs to know: in the worst possible scenario, what is the minimum number of components the robots must remove from the warehouse to guarantee that all the assembly line's requirements are fully met? If the stock is insufficient to guarantee that all targets can be met, the system must signal the impossibility of the operation by printing $$$-1$$$.

Yan is starting a game company! His first creation is a maze puzzle game, where the player needs to reach the target cell in the smallest possible number of steps. The maze is represented by an $$$N \times M$$$ grid and has several types of cells:

• Free cells (.): cells one can freely walk through.
• Walls (#): blocked cells that cannot be walked through.
• Starting position (*): where the player begins.
• Final position (F): the goal to be reached.
• Diagonal walls (\ or /): cells with a wall connecting two opposite corners. It is always possible to enter a cell of this type, but one cannot cross the diagonal wall, which restricts which neighboring cells can be walked to next.

  More specifically, upon entering a cell with a diagonal wall, the possible moves depend on the wall's orientation:

  • In a \ cell, it is possible to move between up and right (U $$$\leftrightarrow$$$ R) or between down and left (D $$$\leftrightarrow$$$ L).
  • In a / cell, it is possible to move between up and left (U $$$\leftrightarrow$$$ L) or between down and right (D $$$\leftrightarrow$$$ R).
• Switches (X): for each diagonal wall, there is exactly one corresponding switch that, when triggered, flips the orientation of that wall (\ becomes / and vice versa). A switch can only be triggered if you are standing on its cell.

The $$$k$$$-th switch X (in reading order, row by row from left to right) is associated with the $$$k$$$-th diagonal wall (also in reading order).

It is allowed to move in the four cardinal directions (U, D, L, R) or trigger the switch on the current cell (X). Each of these actions counts as one move.

Yan wants the final stage to be extremely challenging! Help him by creating a solvable maze of dimensions $$$N \times M$$$ ($$$1 \leq N, M \leq 100$$$) containing at most $$$10$$$ diagonal walls, such that the minimum number of moves needed to solve it is at least $$$10^{5}$$$ steps.

The company Charliebot trades several high-frequency investment strategies on the SBC (Sociedade de Bolsas Computadorizadas). The company cares a great deal about network latency, since the lower it is, the higher the expected return of the strategies.

The fiber optic network currently in use has been mapped into $$$N$$$ points of presence and $$$M$$$ bidirectional links. Charliebot's buy and sell signals originate at its data center (point 1) and need to reach the SBC's co-location facility (point $$$N$$$). For each pair $$$(i,j)$$$ of directly connected points of presence, the latency $$$f_{ij}$$$ in microseconds has been measured.

The network provider has recently installed a bidirectional microwave network between some points of presence and measured its latency as $$$w_{ij}$$$ microseconds. This introduced a new option to reduce latency. However, this network is more expensive, and Charliebot's budget allows hiring at most $$$K$$$ microwave links.

Since a microwave link may need to go around the terrain where it was installed, there is no guarantee that $$$w_{ij} \lt f_{ij}$$$. Furthermore, the network provider guarantees that it will always be possible to find a path in the network even when the budget for microwave links is 0.

What is the smallest possible end-to-end latency, in microseconds?

Nlogônia is implementing a new data transmission system between its $$$N$$$ research stations, numbered from $$$1$$$ to $$$N$$$. The network infrastructure is economical: there are exactly $$$N-1$$$ bidirectional cables connecting the stations, so that there is always a single simple path between any pair of stations.

To ensure that messages reach only those who are actually part of the route, the engineers created a mechanism based on access keys:

1. Each research station will receive a list of access keys.
2. When a station $$$u$$$ sends a message to another station $$$w$$$, the message is signed with all the keys that $$$u$$$ and $$$w$$$ have in common.
3. A station $$$v$$$ can only read and authorize the passage of the message if it possesses all the keys used in that signature. If two stations share no key, any station in the network will be able to read the message.

The security committee established the following rules for the distribution of keys:

• Authorization along the path: Every station $$$v$$$ that lies on the path between $$$u$$$ and $$$w$$$ (including the stations $$$u$$$ and $$$w$$$ themselves) must possess all the keys shared by $$$u$$$ and $$$w$$$.
• Blocking off the path: If a station $$$v$$$ does not belong to the path between $$$u$$$ and $$$w$$$, there must be at least one key shared by $$$u$$$ and $$$w$$$ that station $$$v$$$ does not possess (preventing it from reading the message).
• Economy: The global catalog may contain at most $$$2N$$$ distinct key types in the entire network.

Your task is to help the engineering team determine which keys each station should receive in order to satisfy all the requirements.