Bira's cooking skills have made him famous across the country, earning him an invitation to compete in the prestigious MasterChef: Pastry Edition! For the Halloween episode, he has prepared a mouthwatering tray of donuts and cupcakes. The $$$n$$$ treats are arranged in a single row, represented by a string $$$s$$$: each D represents a donut and each C represents a cupcake.

Just as he finishes, Bira remembers that the judges also care about presentation! This time, they require every segment of five consecutive treats to contain exactly one donut and four cupcakes.

Bira must hurry to rearrange his tray. He may reorder the treats however he likes, but must use every treat he has made, without adding, removing, or changing any of them. Help him find an arrangement that meets the judges' requirement, or determine that it is impossible.

Fred is a professional Catan player. In this board game, players collect resources to build cities and roads. After so many games, he is confident he could find a job in construction if he ever wanted a career change. Today, he wants to broaden his experience by building as many roads as possible!

To build a road, Fred must spend one lumber card and one brick card. He currently has $$$m$$$ lumber cards and $$$t$$$ brick cards. If he runs short of either resource, he can trade with the bank: four lumber cards for one brick card, or four brick cards for one lumber card. He may make as many of these trades as he likes.

Help Fred determine the maximum number of roads he can build using his cards and these trades.

After years of training for programming contests, MkVeio wants a more physically active routine. While looking for an enjoyable activity, he discovers Pilates!

Pilates is an exercise method developed by Joseph Pilates that emphasizes the connection between mind and body. At MkVeio's studio, workouts cycle through four pieces of equipment in this order:

1. Reformer;
2. Cadillac;
3. Chair;
4. Barrel.

1. Reformer	2. Cadillac
3. Chair	4. Barrel

The first workout uses the Reformer, the second the Cadillac, the third the Chair, and the fourth the Barrel. The fifth returns to the Reformer, and the cycle continues.

MkVeio has signed up for $$$n$$$ workouts before the end of the year. He is very disciplined and is certain he will attend them all. Which piece of equipment will he use in his last workout of the year?

In his prime, MkVeio would have written a program to answer this in under a minute, but he is tired and would rather ask for your help.

Matryoshkas are traditional Russian wooden dolls that nest inside one another. Mathias has found a box full of them and wants to put together an exhibition!

The box contains $$$n$$$ separate dolls. Doll $$$j$$$ has size $$$a_j$$$, an integer between $$$1$$$ and $$$n$$$. Several dolls may have the same size.

To assemble a set of size $$$i$$$, Mathias must choose exactly one doll of each size $$$1,2,\ldots,i$$$ and nest them from smallest to largest. Such a set uses $$$i$$$ dolls, and its outermost doll has size $$$i$$$. A single doll of size $$$1$$$ also forms a valid set.

To make the exhibition varied, Mathias wants all the sets to have distinct sizes. Each doll may belong to at most one set, and he does not have to use every doll in the box.

What is the largest number of sets he can assemble?

Laila is going to the theater to see a performance by Clube da Esquina, a celebrated Brazilian musical collective. Unfortunately, something has come up, and she will be the last person to arrive.

The theater has a single row of $$$n$$$ seats, numbered from $$$1$$$ to $$$n$$$, with an aisle at each end. The aisles are represented by positions $$$0$$$ and $$$n+1$$$. The distance between positions $$$i$$$ and $$$j$$$ is $$$|i-j|$$$.

The show is sold out. The $$$n-1$$$ people arriving before Laila enter one at a time and are extremely antisocial: each wants to sit as far as possible from both the people already seated and the aisles.

The comfort of an empty seat is the minimum distance from that seat to any occupied seat or aisle, measured when the person chooses their seat. Each person chooses an empty seat with maximum comfort. If several seats tie, they may choose any of them.

On her way to the theater, Laila can think of only one thing: which seat will be left for her?

For each seat $$$k$$$, from $$$1$$$ to $$$n$$$, determine how many sequences of choices by the $$$n-1$$$ people leave that seat empty. Two sequences are different if the seat chosen at some step differs. Since the answers may be large, print each answer modulo $$$998244353$$$.

While preparing a problem for the $$$3\text{D}(\text{C}^{4})$$$ contest, Emanuel became interested in abbreviations. Some seem intuitive to him, while others do not. He has asked you to write a program to tell them apart.

A string $$$t$$$ is an intuitive abbreviation of a string $$$s$$$ if $$$t$$$ can be obtained by deleting zero or more characters from $$$s$$$ without changing the order of the remaining characters. Each occurrence of a letter in $$$t$$$ must correspond to a distinct occurrence in $$$s$$$.

For example, DDDDC is an intuitive abbreviation of DIRTYDEEDSDONEDIRTCHEAP, and DCC is an intuitive abbreviation of DINOSSAUROCODECUP.

For each test case, determine whether the second string is an intuitive abbreviation of the first.

FIFA is organizing a football tournament with a group stage. One group contains $$$n$$$ national teams, numbered from $$$1$$$ to $$$n$$$. Each pair of teams in the group will play exactly once.

A win awards $$$3$$$ points to the winning team and $$$0$$$ to the losing team. A draw awards $$$1$$$ point to each team.

Your friend Pedro claims that this group will be so evenly matched that all $$$n$$$ teams will finish the group stage tied on exactly $$$k$$$ points. You want to find out whether this is possible.

"Stoppage time: until they equalize!"

Given $$$n$$$ and $$$k$$$, determine whether results can be assigned to the $$$\frac{n(n-1)}{2}$$$ matches so that every team finishes with exactly $$$k$$$ points. If so, print any set of results that demonstrates this.

Professor G. Coutinho wrote his old proofs for Phantasmagorical Graph Theory in English, using the field's standard notation. For example, the Greek letter $$$\alpha$$$ always refers to independent sets, while $$$\chi$$$ refers to proper colorings. Now he is teaching the course again, this time in Portuguese.

Some frightening graphs from Phantasmagorical Graph Theory

Since he is very busy, he has asked his old friend Gepeto to help translate his notes. Gepeto, however, is rather absent-minded: he does not remember the notation well and tends to mix up the symbols as he translates. This has made the lectures very confusing, and Coutinho wants to decide whether he should translate the notes himself.

He asks each student which symbols they consider essential and which substitutions they could tolerate. He then wants to count the ways Gepeto could mix up the notation so that every student is confused: the worst possible outcome.

Formally, there are $$$n$$$ standard symbols, numbered from $$$1$$$ to $$$n$$$, and $$$m$$$ students. For each student $$$i$$$, the set $$$A_i$$$ contains the symbols that student considers essential. Gepeto replaces the symbols according to a permutation of the $$$n$$$ symbols. Student $$$i$$$ is confused if at least one symbol in $$$A_i$$$ is replaced by a different symbol. Count the permutations that confuse every student.

Professor Coutinho is not known for his programming skills, so he has left this task to you. Help him!

Luisa Lopes is studying for her Software Engineering exam and has gotten stuck on the SOLID principles, which underpin the course.

To help the ideas sink in, she decides to examine the dependency graph of a legacy project she maintains as a freelancer. Each vertex represents a module, and a directed edge from $$$u$$$ to $$$v$$$ means that module $$$u$$$ depends directly on module $$$v$$$. A well-designed project should have no cyclic dependencies: no module should depend, directly or indirectly, on itself. Luisa suspects that her project has exactly this problem.

Thinking about the "D" in SOLID, the Dependency Inversion Principle, she starts wondering about reversing dependencies. Could reversing a single dependency eliminate all the cycles at once?

With little time left before her exam, Luisa asks for your help. Given a directed graph $$$G$$$, determine whether it can be made acyclic by reversing at most one edge. Reversing an edge $$$u \to v$$$ means replacing it with $$$v \to u$$$.

Magner Weira has a server with $$$n$$$ components. Each component works only within a certain temperature range: component $$$i$$$ tolerates temperatures from $$$l_i$$$ to $$$r_i$$$, inclusive. If the temperature leaves this range, the component burns out permanently.

Magner has been so busy that he has neglected the server for $$$m$$$ days. Worried that some components may have burned out, he checks the room's temperature records. The only available record lists the minimum temperature $$$a_j$$$ and maximum temperature $$$b_j$$$ reached on each day $$$j$$$.

For each component, determine the first day on which it burned out, or report that it is still working after these $$$m$$$ days.

Manuel loves puzzles and is trying to solve one involving a row of $$$n$$$ dominoes, each placed vertically. Initially, the positions are numbered from $$$1$$$ to $$$n$$$ from left to right.

The domino initially at position $$$i$$$ has number $$$a_i$$$ on its upper half and number $$$b_i$$$ on its lower half. Across all $$$2n$$$ halves, each integer from $$$1$$$ to $$$2n$$$ appears exactly once.

Each domino also has a color, represented by an integer. The domino initially at position $$$i$$$ has color $$$c_i$$$. Manuel may perform either of the following operations any number of times:

• Choose a domino and swap the numbers on its upper and lower halves.
• Choose two dominoes of the same color and swap their positions in the row.

His goal is to arrange the dominoes so that, when read from left to right, both the upper numbers and the lower numbers form strictly increasing sequences.

Before performing any operations, Manuel may repaint some dominoes. Each repainted domino may be assigned any integer color from $$$1$$$ to $$$n$$$.

Determine the minimum number of dominoes he must repaint to solve the puzzle. If it is impossible regardless of which dominoes he repaints and which colors he chooses, print $$$-1$$$.

Today is an important day for Matheus "Mathias" Prates: he is taking his final exam in AL2 (Cool Algorithms 2). He arrived early at the Federal University of Minas Gerais (UFMG) to study in the science library, but got so caught up in the review exercises that he is now late for lunch at his favorite campus restaurant, Gula Mineira.

Gula Mineira serves a self-service buffet with $$$n$$$ dishes arranged on a circular table. The table is represented by a circular list: position $$$i$$$ holds the dish identified by the positive integer $$$p_i$$$. Each dish appears at exactly one position.

Matheus has written down a sequence $$$s$$$ of the dishes he would like to take, in the order he wants to add them to his plate. Unfortunately, the restaurant is crowded, and everyone must move around the table in the same direction. If he is at position $$$i$$$ at time $$$t$$$, he may move to the next position ($$$i+1$$$, or $$$1$$$ if $$$i=n$$$), arriving at time $$$t+1$$$, or leave the queue. Leaving and rejoining the queue takes $$$k$$$ seconds and allows him to rejoin at any position. Taking a serving of a dish, even repeatedly, takes no time.

Initially, Matheus is outside the queue and may join at any position for free. Every subsequent departure and reentry costs $$$k$$$ seconds.

He wants to take as many dishes from his wish list as possible, in the listed order, within $$$w$$$ seconds. More formally, he wants to take a longest possible subsequence of $$$s$$$ within this time limit. Dishes skipped in the subsequence need not be visited. Help him finish lunch in time for his exam!

After conquering many cities, the king of Nlogonia has decided to reward his vassals for their loyalty and success in battle. The conquered territory consists of $$$n$$$ cities connected by bidirectional roads. He wants to divide it among $$$v$$$ vassals so that each vassal controls at least one city and each city is controlled by exactly one vassal.

However, the vassals are quick-tempered and will seize any excuse to quarrel. To keep the peace, the king imposes a rule: each city may have at most one road leading to a city controlled by a different vassal.

Fortunately, the cities form a tree: there is exactly one path between any pair of cities, and there are no road cycles.

The king is busy with his royal duties and has asked you, the finest programmer in Nlogonia, to determine whether such a division is possible. If it is, also provide a valid assignment of cities.

Luis Higino has just returned from a long trip to Campinas, Brazil. During his stay, he visited the Institute of Computing at the University of Campinas (Unicamp) and was struck by this wall:

He liked it so much that he decided to recreate the artwork at home! He hired Cláudio to print four stickers:

1. A box (an unfilled rectangle).
2. The word THINK.
3. The words THE BOX, one above the other.
4. The word OUTSIDE.

Treat the box's outline as having negligible thickness. Represent each text sticker by its bounding box, the smallest rectangle containing the text. The dimensions are shown below.

The box has height $$$a_1$$$ and width $$$l_1$$$; THINK has height $$$a_2$$$ and width $$$l_2$$$; THE BOX has height $$$a_3$$$ and width $$$l_3$$$; and OUTSIDE has height $$$a_4$$$ and width $$$l_4$$$. The dashed lines show the text bounding boxes.

Luis's wall has height $$$a_p$$$ and width $$$l_p$$$. The arrangement must satisfy these conditions:

• The bounding boxes of THINK and THE BOX must fit entirely inside the box, without overlapping interiors.
• The rectangle enclosed by the box and the bounding box of OUTSIDE must fit entirely on the wall, without overlapping interiors.
• No element may be rotated.

Boundaries may touch. Subject to these rules, the stickers may be placed anywhere. Given the dimensions of the four stickers and the wall, determine whether Luis can recreate the artwork.