In this problem we will be dealing with character sequences, often called strings. A sequence is non-trivial if it contains at least two elements.

Given a sequence $$$s$$$, we say that a chunk $$$s_i, \ldots, s_j$$$ is monotone if all its characters are equal, and we say that it is maximal if this chunk cannot be extended to left or right without losing the monotonicity.

Given a sequence composed only of characters "a" and "b", determine how many characters "a" occur in non-trivial maximal monotone chunks.

Alice and Bob will play a game with $$$3$$$ piles of stones. They take turns and, on each turn, a player must choose a pile that still has stones and remove a positive number of stones from it. Whoever removes the last stone from the last pile that still had stones wins. Alice makes the first move.

The $$$i$$$-th pile will have a random and uniformly distributed number of stones in the range $$$[L_i, R_i]$$$. What is the probability that Alice wins given that they both play optimally?

A laser cutting machine for wood sheets has a laser head that can move in only two directions, horizontal and vertical. You have been hired to be part of the testing team for the machine.

One of the tests consists of programming the machine to perform a non-empty sequence of consecutive cuts that starts and ends at the same point. Each cut in the sequence, except the first, starts at the point at which the previous cut ended. No cuts touch the edge of the sheet to be cut. Figures (a) and (b) below show two examples of cutting sequences, with respectively 8 and 14 cuts.

Your boss asked you to determine the area of the largest piece produced by the sequence of cuts, disregarding the piece attached to the edges of the cut sheet. That is, only the pieces contained in the polygon formed by the cut lines should be considered. Figures (c) and (d) below show respectively the largest pieces produced by the cuts of figures (a) and (b).

To illustrate, figures (e) and (f) below show the discarded piece (which contains the edges of the wood sheet) of the cut sequences of figures (a) and (b), respectively.

A square has its vertices at the coordinates $$$(0, 0), (0, 2^N), (2^N, 2^N), (2^N, 0)$$$. Each vertex has an attractor. A particle is placed initially at position $$$(2^{N-1}, 2^{N-1})$$$. Each attractor can be activated individually, any number of times. When an attractor at position $$$(i, j)$$$ is activated, if a particle is at position $$$(p, q)$$$, it will be moved to the midpoint between $$$(i, j)$$$ and $$$(p, q)$$$.

Given $$$N$$$ and a point $$$(x, y)$$$, calculate the least number of times you have to activate the attractors so that the particle ends up at position $$$(x, y)$$$. You may assume that for all test cases a solution exists.

An enormous number of balloons are floating about in the Convention Hall after the Awarding Ceremony of the ICPC Subregional Contest. The manager of the Convention Hall is angry, because he will host another event tomorrow and the balloons must be removed. Fortunately this year Carlinhos came prepared with his bow and arrows to pop the balloons.

Also, luckily, due to the air conditioning flow, the balloons are all in the same vertical plane (that is, a plane parallel to a wall), although in distinct heights and positions.

Carlinhos will shoot from the left side of the convention hall, at a chosen height, in the direction of the right side of the Convention Hall. Each arrow moves from left to right, at the height it was shot, in the same vertical plane of the balloons. When an arrow touches a balloon, the balloon pops and the arrow continues its movement to the right, at a height decreased by 1. In other words, if the arrow was at height $$$H$$$, after popping a balloon it continues at height $$$H - 1$$$.

Carlinhos wants to pop all balloons shooting as few arrows as possible. Can you help him?

The Multidimensional Hangman Game has very peculiar rules. In a way, it is like you are playing several games of the traditional Hangman game at the same time, with the difference that the words don't have to exist in the dictionary. If you've never played Hangman, don't worry: all the information you need is below.

In the multidimensional version of the game, there are several words on a board, initially unknown, all of the same length. At each turn in the game, you discover some characters from certain word positions (how these characters were discovered is not important for this problem). At a certain point, when only one unknown character remains in each word on the board, the game goes into the all or nothing phase. At this point, you must choose a word that maximizes the number of compatibilities with the words on the board. For a choosen word $$$P$$$, we say it is compatible with a word $$$T$$$ on the board if all known letters in $$$T$$$ occur in exactly the same positions in $$$P$$$.

Given the known information about the words on the board, you must determine which word to choose for all or nothing phase, which maximizes the number of compatibilities. If there is more than one solution, print the lexicographically smallest. We say that a word $$$P$$$ is lexicographically smaller than a word $$$Q$$$ if $$$P_i \lt Q_i$$$ where $$$P_i$$$ is the i-th character of $$$P$$$, $$$Q_i$$$ is the i-th character of $$$Q$$$ and $$$i$$$ is the smallest index such that $$$P_i \neq Q_i$$$.

Every polygon can be constructed by joining triangles. In particular, we can do this iteratively: we start with a triangle, we add a second triangle identifying one of its sides to one of the sides of the initial triangle, we add a third triangle identifying one of its sides to one of the free sides of one of the original triangles, and so on. We will only consider polygons that can be constructed in this way, where each added triangle touches (and is identified with) exactly one side of a previously positioned triangle.

Given a polygon $$$P$$$, let $$$T$$$ be the set of triangles used to form it. The sides of each triangle are line segments. Let $$$L$$$ be the set of segments that are sides of some triangle in $$$T$$$. Note that each element of $$$L$$$ is one side of one or two elements of $$$T$$$.

Once we have a polygon positioned in the plane, in some cases we can remove some of the triangles that compose it, without changing the set $$$L$$$. We want to remove triangles so that the set $$$L$$$ is maintained and the total area of the remaining triangles is minimal. Equivalently, we want to select a subset $$$S$$$ of triangles from $$$T$$$ such that:

1. Every element of $$$L$$$ is the side of at least one triangle in $$$S$$$; and
2. The sum of the areas of the elements of $$$S$$$ is as small as possible.

The president of Nlogonia decided, by decree, that all the streets of Nlogonia should be one-way. Due to the lack of knowledge of elementary science, there was no proper planning for the changes. After the new system came in place, people would not be able to go to work, or would not be able to return home from work, for example. As a result, there was chaos and riots in lots of cities.

The president was impeached and the new administration of the country hired a team of scientists to solve the problem. In turn, the committee hired you, an expert in complexity of algorithms, to help them with the efficient computation of solutions.

So, for each city, you are given the reference points of the city, and the one-way streets, each of which connects two reference points. Your task is to determine the minimum number of one-way bridges that must be built in order to have full connectivity in the city. Each bridge should also connect two reference points.

Spies Breaching Computers (SBC) is a private digital spy agency that is developing a new device for intercepting information using electromagnetic waves, which allows spying even without physical contact with the target.

The device tries to collect information one byte at a time, this is, a sequence of 8 bits where each of them, naturally, can have a value of 0 or 1. In certain situations, due to interference from other devices, the reading cannot be done successfully. In this case, the device returns the value 9 for the corresponding bit, informing that the reading could not be performed.

In order to automate the recognition of the information the device reads, a request was made for a program that, based on the information read by the device, informs whether all bits were read successfully or not. Your task is to write this program.

Twenty-three is a simple card game played by kids. Like its name suggests, it is a variation of Blackjack, which is the most widely played game in casinos and gaming sites.

The game uses a deck of 52 cards, with four suits, each suit with 13 cards (ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen and king). Card suits are not relevant. The picture cards (jack, queen and king) are worth ten points, cards with numbers are worth their number in points (for example, the 4 card is worth four points) and the ace is worth one point.

The player who has the most points wins, provided it does not exceed 23. If a player has a number of points greater than 23 we say the player busts.

The game rules are simple: at each game, initially the deck is shuffled, the cards are placed in a stack and each player receives two cards from the stack. All cards are dealt face up (all players see all players' cards). The next step, called round, is repeated as long as there are active players: a card is taken from the stack and set on the table face up. This card, called common card, counts to all players. If a player busts, he leaves the game. The winner is the player that in a given round has a total of 23 points (considering their two starting cards plus the common cards), or if the player is the only active player at the end of the round. Note that there can be more than one winner (whose cards add up to 23) and that there may be no winner in a match.

John and Mary are playing twenty-three. The two are the only players in the game, neither of them busted and neither of them has 23 points. Furthermore, the players score is such that the next common card may cause the game to end.

Given John and Mary initial cards and the common cards, determine the lowest possible value of a card that should be taken from the stack in the next round for Mary to win the game.

Kalel is a frog that likes jumping over stones.

There are $$$N$$$ stones in a row, numbered from $$$1$$$ to $$$N$$$ from left to right. Kalel begins at stone $$$1$$$ and he wants to reach stone $$$N$$$.

At each move, Kalel can choose among $$$M$$$ types of jump. The $$$j$$$-th jump allows him to jump from stone $$$x$$$ to stone $$$x + d_j$$$ and costs $$$p_j$$$ energy points. It may happen that $$$p_j$$$ equals $$$0$$$ for some $$$j$$$. You can assume Kalel never runs out of energy.

Given $$$N$$$ and $$$K$$$, calculate in how many ways Kalel can reach stone $$$N$$$ spending at most $$$K$$$ energy points in total. Two ways are considered different if the sequence of jump choices is different. As this number can become very large, we are only interested in its remainder modulo $$$10^9$$$ (one billion).

A tree is a graph that is connected (there exists a path between any two of its vertices), undirected (the edges of the graph have no direction), and acyclic (there are no cycles).

A colorful tree is a tree in which each of its vertices has a specific color.

A tedious path is a path in the tree such that both the initial and final vertices have the same color, and there is no vertex or edge that appear more than once in the path. Note that the color of the intermediate vertices, if there are any, are irrelevant.

Given a colorful tree, with $$$N$$$ vertices, your task is calculate, for each of the edges, the number of tedious paths that go through that edge.

October 8th, 2022. This is the date of the most awaited event of the year by computer science students across the country. No, we are not talking about ICPC.

We are talking, of course, about Hopscotch! For those unfamiliar, Hopscotch is an annual competition traditionally held as an ICPC side event. Live streamed to spectators from all continents, and to practitioners of the most esoteric programming languages, this exotic variant of the popular children's game takes place in an infinite, spiral-shaped court, subdivided into sequentially numbered areas starting at zero, as depicted below.

This year, Hopscotch has attracted a record number of $$$N$$$ participants, numbered sequentially from $$$1$$$ to $$$N$$$. It is known that the $$$i$$$-th participant starts in the area numbered $$$A_i$$$.

Hopscotch consists of $$$Q$$$ rounds. During the $$$q$$$-th round, Carlão, beloved Hopscotch organizer for longer than anyone can remember, will communicate two integers to participants: $$$c_q$$$ and $$$d_q$$$. This is an order for all participants with identifying number $$$i$$$ such that $$$i$$$ and $$$c_q$$$ share a common integer factor larger than $$$1$$$ to retrogress $$$d_q$$$ positions in the Hopscotch court, one by one, never going back further than position $$$0$$$. (Any participant who eventually returns to position $$$0$$$ should remain there indefinitely, ignoring any further retrogress commands, so as not to leave the court.)

Under the assumption that the participants have executed the instructions perfectly (they would never want to disappoint Carlão), your task is to determine, for each participant, the number of the round in which he or she returns to position $$$0$$$ (or otherwise indicate that this never happens).

You have just won a deck of cards with $$$N$$$ cards. Each of these cards has two numbers written on it: one on the front side, and another on the back side.

Your friend has challenged you to a game. He shuffled the cards and put them on a table. The cards are laid out on a line, side by side, with the front side facing up.

From left to right, you know that the number written on the front side of the $$$i$$$-th card is $$$A_i$$$, and that the number written on the back side of the $$$i$$$-th card is $$$B_i$$$.

The game is divided into two parts.

In the first part you should pick $$$K$$$ cards of the deck. To pick a card, you have to choose either the first card on the left, or the first card on the right of the table, and take it for you.

After that, you have to choose $$$L$$$ of the cards you picked up and flip them.

Your score will be equal to the sum of the numbers written on the front side of all of the $$$K$$$ cards you picked, plus the sum of the numbers written on the back side of the $$$L$$$ cards you flipped.

The goal? To achieve the highest possible score, of course!