At UFBA, Marina is trying to decide on which days she should attend a demanding review session before the next GruPro selection contest.

For each of the next $$$N$$$ days, attending on day $$$i$$$ gives her a benefit of $$$a_i$$$, which may even be negative if she is already too exhausted.

If Marina attends on several consecutive days, that forms a single streak. A streak of length $$$L$$$ causes a fatigue penalty of $$$L^2$$$. In other words, if the attended days are partitioned into maximal consecutive streaks of lengths $$$L_1, L_2, \ldots, L_k$$$, then her final score is $$$$$$\left(\sum \text{benefit of all attended days}\right) - \left(L_1^2 + L_2^2 + \cdots + L_k^2\right). $$$$$$

She may skip any days she wants. After all, everyone needs a break sometimes; nobody is made of steel.

Determine the maximum possible final score.

During a cultural fair at UFBA, a group of students is preparing souvenir ribbons inspired by the famous fitinhas do Bonfim. Each ribbon design is encoded by an integer, and its binary representation tells which ornaments are present: a bit equal to $$$1$$$ means that ornament is used, while a bit equal to $$$0$$$ means it is not. Therefore, the total number of ornaments in a design is exactly the number of bits set to $$$1$$$.

Professor Rubis wants to approve the next design after a given code $$$N$$$, but he is strict about one detail: the new design must contain exactly $$$M$$$ ornaments. Among all valid integers strictly greater than $$$N$$$, he wants the smallest possible one, so that the next approved design is as close as possible to the current code.

Help him find that next ribbon code.

When the former Big Brother Brazil contestant Davi Brito dropped the phrase "Calma, Calabreso", the internet did what it always does: it turned the moment into an endless stream of edits, reactions, and inside jokes. The meme became so big that it even inspired a Davi Brito lookalike contest at UFBA, which awarded a "kit calabresa" (lá ele!) prize.

To celebrate the chaos, his fans assembled a "calabreso panel" from screenshots, reactions, captions, and meme fragments arranged in a matrix. Each cell stores an integer representing the type of content placed in that position.

A rectangular part of the panel is calm if it still looks exactly the same after a rotation of $$$180^\circ$$$. In other words, if you rotate the rectangle by half a turn, every cell must match the cell that moves into its place. So the top-left corner must match the bottom-right corner, the top-right corner must match the bottom-left corner, and so on.

Some parts of the panel are almost symmetric, but not quite. Others are perfectly balanced, as if even the meme itself had decided to calm down.

Your task is to find the maximum possible area of a calm submatrix.

Formally, a submatrix defined by corners $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$ is calm if $$$$$$ A_{i, j} = A_{i_1 + i_2 - i, j_1 + j_2 - j} $$$$$$ for every cell $$$(i, j)$$$ inside the submatrix.

Every February, the streets of Salvador surrender to the Carnaval, and no one feels it more than DJ Sandália, the legendary selector who rides the oldest trio elétrico circling the Campo Grande circuit. The folião crowd shouts song requests all night long, and DJ Sandália has carefully written down, for each of the $$$N$$$ songs in the repertoire, an integer "weight" $$$P_i$$$ that measures how badly the crowd wants to hear song $$$i$$$.

To keep the party fair, DJ Sandália wants to pick the next song at random so that song $$$i$$$ is chosen with probability exactly $$$P_i / (P_1 + P_2 + \dots + P_N)$$$.

There is just one problem: the trio's randomizer is a battered piece of hardware from the 1980s, and the only thing it knows how to do is to draw an integer uniformly at random from a given range. It cannot weight anything by itself; every draw it produces is perfectly uniform.

Working only with this uniform randomizer, DJ Sandália came up with the following strategy. First, choose a single integer $$$K$$$ and build three arrays $$$A$$$, $$$B$$$ and $$$C$$$, each of length $$$N$$$. Then, to pick a song:

• draw $$$x$$$ uniformly from $$$1$$$ to $$$N$$$;
• draw $$$y$$$ uniformly from $$$0$$$ to $$$K$$$;
• if $$$y \lt C_x$$$, play song $$$A_x$$$; otherwise, play song $$$B_x$$$.

Help DJ Sandália choose $$$K$$$ and the arrays $$$A$$$, $$$B$$$ and $$$C$$$ so that this procedure plays song $$$i$$$ with probability exactly $$$P_i / (P_1 + \dots + P_N)$$$, for every song $$$i$$$.

The city of Salvador, in Bahia, is famously hilly, and its blocks are laid out on a regular grid. We model the whole neighborhood as the infinite integer grid: every grid point has integer coordinates and is a corner where blocks meet.

A courier from a UFBA student delivery group starts at corner $$$A = (a_x, a_y)$$$ and must reach corner $$$B = (b_x, b_y)$$$. In one minute the courier can walk one block to an orthogonally adjacent corner, that is, from $$$(x, y)$$$ to any of $$$(x+1, y)$$$, $$$(x-1, y)$$$, $$$(x, y+1)$$$ or $$$(x, y-1)$$$. Each such move costs exactly $$$1$$$ minute.

Besides the ordinary grid, Salvador also has $$$M$$$ special perfectly straight slanted streets, each running at exactly $$$45$$$ degrees. Each slanted street is described by a pair $$$(k, d)$$$ with $$$d \in \{+1, -1\}$$$:

• If $$$d = +1$$$, the street is the line $$$y = x + k$$$. While standing on a grid point of this street, the courier may, in addition to the ordinary moves, step to $$$(x+1, y+1)$$$ or $$$(x-1, y-1)$$$ in one minute, staying on the street.
• If $$$d = -1$$$, the street is the line $$$y = -x + k$$$. While standing on a grid point of this street, the courier may, in addition to the ordinary moves, step to $$$(x+1, y-1)$$$ or $$$(x-1, y+1)$$$ in one minute, staying on the street.

These extra slanted steps are available only while the courier is currently on a grid point that belongs to the corresponding slanted street. Every move, ordinary or slanted, costs exactly $$$1$$$ minute.

For example, suppose $$$A = (0, 0)$$$, $$$B = (3, 3)$$$, and there is a single slanted street $$$(k, d) = (0, +1)$$$, the line $$$y = x$$$. The courier can ride this street from $$$A$$$ to $$$B$$$ in $$$3$$$ minutes:

Help the group find the minimum number of minutes needed to travel from $$$A$$$ to $$$B$$$.

The GruPro (Grupo de Programaçao da UFBA) wants to install a new drinking fountain on the Ondina campus, somewhere among the wooded paths between the Instituto de Computação and the Restaurante Universitário.

The campus map is an integer grid. There are $$$N$$$ benches, and the $$$i$$$-th bench sits at integer coordinates $$$(x_i, y_i)$$$. To be fair to everyone, the students decided the fountain must be placed exactly halfway between two benches: that is, at the midpoint of some pair of distinct benches $$$i$$$ and $$$j$$$, $$$$$$\left( \frac{x_i + x_j}{2},\ \frac{y_i + y_j}{2} \right). $$$$$$

Underground pipes can only reach points with integer coordinates, so the chosen midpoint must land exactly on a grid point.

Help the GruPro pick two benches whose midpoint is a valid spot for the fountain, or tell them it is impossible.

Welcome to GruPro's Golden Challenge! You are a competitive programmer beginning your journey through UFBA's training curriculum. Your programming journey starts with an initial score of $$$X$$$, and ahead of you lies a series of $$$N$$$ training challenges, each designed to test and refine your programming abilities in different areas.

However, you have the freedom to choose the order in which you tackle challenges. Each challenge $$$i$$$ has two attributes:

• Score Limit ($$$P_i$$$): The maximum score you can achieve after completing this challenge;
• Score Change ($$$Q_i$$$): The amount your score changes upon completion (can be positive or negative).

When you complete challenge $$$i$$$, your score evolves according to:

$$$$$$ X \leftarrow \min(P_i, X + Q_i) $$$$$$

In other words, your score is adjusted by $$$Q_i$$$ points (which can be a gain or a penalty), but your total score cannot exceed the limit $$$P_i$$$ for that challenge. Some challenges reward you generously while others penalize careless approaches.

Your mission is to complete all $$$N$$$ challenges in the optimal order to maximize your final score. Choose wisely, and you might just achieve the ultimate victory!

Marina is in the final stretch of her degree at UFBA. After years of balancing classes, deadlines, and endless cups of coffee, she has only one goal left: graduate as soon as possible.

To do that, she must complete all $$$N$$$ required disciplines of her curriculum, numbered from $$$1$$$ to $$$N$$$. At first, her plan seemed simple: whenever a semester begins, she would enroll in every discipline she is already allowed to take. There is no villain in this story, no unexpected internship, no exchange program, and no dramatic plot twist. There is only Marina, her graduation requirements, and the one force capable of turning any peaceful academic plan into chaos: SIGAA.

Some disciplines, of course, depend on others. There are $$$M$$$ prerequisite relations, and each relation $$$(u, v)$$$ means that Marina must complete discipline $$$u$$$ before she is allowed to take discipline $$$v$$$. In principle, this should define a sensible curriculum structure. In practice, when SIGAA is involved, Marina would not be entirely surprised if somehow a later discipline ended up demanding an earlier one, which then demanded another one, which eventually demanded the first again.

As if that were not enough, not every discipline is offered every semester. Sometimes departments change plans, sometimes classes do not open, and sometimes SIGAA behaves in ways that students prefer not to question too deeply. There are $$$K$$$ temporary restrictions, and each restriction $$$(j, x)$$$ means that discipline $$$x$$$ is not offered in semester $$$j$$$. So even if Marina is fully ready to take a discipline, SIGAA may simply decide that semester is not the chosen one.

In any semester, Marina may take any number of disciplines, as long as:

• every prerequisite of each chosen discipline was completed in an earlier semester, and
• the discipline is offered in that semester.

Help Marina determine the minimum number of semesters she needs to finish all disciplines, survive the bureaucratic maze, and finally graduate. If graduation is impossible, output $$$-1$$$ and accept that Marina will remain trapped in UFBA forever, eventually becoming yet another legendary campus animal.

João is about to visit Bahia for the first time. He has already planned everything: walking through Pelourinho, eating a lot of acarajé, going to the beach, and learning a few local expressions before he arrives. However, his friends from Salvador warned him that's not enough. According to them, anyone who wants to survive the first few conversations must first pass a small informal test.

They explained one of the rules to him (and the most important one): in some playful situations, a word ending with the letter 'u' is changed to avoid an unfortunate rhyme. So, before the trip, João has to practice this transformation correctly.

The transformation is as follows:

• if the word ends with 'u', remove that final 'u' and append 'ivis';
• otherwise, keep the word unchanged.

For example, 'caju' becomes 'cajivis', while 'acarajé' remains 'acarajé'.

Given a word, help João produce the correct Bahia-style version and pass the test.

It is Carnaval in Salvador, and a bloco afro is about to parade down the slopes of the Pelourinho with its unmistakable samba-reggae groove.

The bloco is formed by $$$N$$$ pairs of percussionists. In the $$$i$$$-th pair, the surdo player strikes $$$A_i$$$ beats per measure, while the caixa player next to them strikes $$$B_i$$$ beats per measure. For the whole bloco to lock into a single, hypnotic groove all the way to the Largo do Pelourinho, the maestro wants every pair to produce the same total number of beats per measure.

Formally, the maestro picks a target value $$$C$$$ and wants $$$A_i + B_i = C$$$ to hold for every pair $$$i$$$. He is free to choose any $$$C$$$ he likes.

To achieve that, he can call rehearsals. In a single rehearsal he picks one drummer (either the surdo or the caixa of any pair) and retunes their pattern to play exactly $$$X$$$ beats per measure, where $$$X$$$ is any integer with $$$1 \leq X \leq 10^{9}$$$. Notice each rehearsal may use a different value of $$$X$$$.

Help the maestro find the minimum number of rehearsals needed so that all the pairwise sums become equal.

At UFBA, a student group is organizing a festival menu and wants to measure the strength of different consecutive stretches of dishes. For each position $$$i$$$, the value $$$A_i$$$ represents how much that dish contributes to the overall dendê power of the menu. The power of a contiguous segment is the sum of all values inside it.

Everyone already knows how to find the single strongest segment. But for the final ranking, the organizers need more than just the best one: they want the $$$K$$$-th strongest segment.

Can you help them find the power of the $$$K$$$-th strongest segment?

During a GruPro meeting at UFBA, an unfortunate joke started spreading through a friendship network. The network forms a tree with $$$N$$$ students, numbered from $$$1$$$ to $$$N$$$.

Each student is currently in one of two moods:

• $$$0$$$: Calm, and will let the joke pass;
• $$$1$$$: Suspicious, and will immediately answer "lá ele!".

When a story travels through the unique simple path between two students, every suspicious student on that path would react. However, there is an important Bahian rule: once someone says "lá ele!", everyone in the same consecutive suspicious stretch becomes protected, so no extra "lá ele!" is needed until the path reaches a calm student again.

As the meeting goes on, people may change their mood after hearing new context, remembering an older joke, or deciding that the conversation was actually harmless. Because of that, the current mood of a student is not fixed forever.

You must process two types of operations:

• Update the mood of one student;
• Given two students $$$u$$$ and $$$v$$$, compute how many times "lá ele!" is said along the path from $$$u$$$ to $$$v$$$.