The Tengo-lengo-tengo Football Federation (FFT) is organizing the Tengo-lengo-tengo World Cup, a tournament unlike anything ever seen before. For the opening show, the organizers placed a line of $$$N$$$ flags on the field. The $$$i$$$-th flag represents one of the teams in the cup and has an integer $$$A_i$$$ written on it.

During the show, flags will be removed from the field through arretada removals. A removal is called arretada when the opening crew chooses a non-empty segment of consecutive flags, say from position $$$L$$$ to position $$$R$$$, such that: $$$$$$\gcd(A_L, A_{L+1}, \ldots, A_R) \gt 1 $$$$$$ Here, $$$\gcd$$$ denotes the greatest common divisor of the involved numbers. In an arretada removal, all flags in that segment are removed. After that, the remaining flags close the gap, keeping the same relative order as before.

One possible sequence of removals for the second sample. In each row, the highlighted flags are removed.

To plan the opening show properly, the FFT wants to know the minimum number of arretada removals needed to remove all flags during the presentation.

In the final of the Tengo-lengo-tengo Football World Cup, the stadium light show is the highlight of halftime while several artists perform on stage. Each spotlight configuration is represented by a binary number with exactly $$$3$$$ bits: bit $$$0$$$ means a light is off, and bit $$$1$$$ means a light is on.

To make the halftime show look smooth, the organizers want the lights to change calmly. Therefore, from one configuration to the next, exactly one spotlight must change state.

You are given an initial configuration $$$X_0$$$. Your task is to produce a sequence that starts at $$$X_0$$$, visits all $$$8$$$ configurations of $$$3$$$ bits exactly once, and then returns to $$$X_0$$$.

A football club is reorganizing its youth divisions to take part in a championship organized by the FFT, the Tengo-lengo-tengo Football Federation.

There are $$$N$$$ available professionals, and each professional has a main role in a coaching staff.

Roles are represented by integers. For example, role $$$1$$$ may represent a head coach, role $$$2$$$ a fitness coach, role $$$3$$$ a physiotherapist, role $$$4$$$ a performance analyst, and role $$$5$$$ a goalkeeper coach.

The $$$i$$$-th professional has role $$$A_i$$$.

The club wants to divide all $$$N$$$ professionals into exactly $$$K$$$ coaching staffs, one for each youth division.

However, to avoid repeated responsibilities within the same staff, a coaching staff cannot contain two professionals with the same role. Also, every coaching staff must contain at least one professional.

Two divisions are considered different if there exists some group of professionals that forms a coaching staff in one division but does not form a coaching staff in the other. The order of the coaching staffs does not matter, and the order of professionals inside the same staff does not matter either.

Determine the number of different ways to form the $$$K$$$ coaching staffs, modulo $$$998244353$$$.

The year is 3026, and the artificial intelligence GaLaDOS is about to take over the world. Fortunately, humanity has one last chance: it was discovered that the AI shared an administrator password with its allies. If this password is recovered, the AI can be shut down and humanity will be saved.

Of course, things will not be that easy. First, GaLaDOS defined two numbers, $$$N$$$ and $$$K$$$. Then the password $$$X$$$, initially a number between $$$0$$$ and $$$2^{32}-1$$$, went through the following encryption process $$$N$$$ times:

1. Let $$$Y$$$ be the value of $$$X \oplus (X \cdot 2^{K})$$$.
2. Change $$$X$$$ to be the value of the first $$$32$$$ bits of $$$Y$$$.

Here, $$$\oplus$$$ represents the XOR operation* between two numbers.

Your goal is: given $$$N$$$, $$$K$$$, and the final result of the encryption $$$S$$$, build a decoder that returns the original password $$$X$$$. If there is more than one valid password, you may return any of them.

* The XOR operation between two numbers is the result of the exclusive OR between the bits of their binary representations. For example: $$$5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$$$.

This is an interactive problem.

At the Caruaru Fair, famous for its clothing stalls, a vendor set aside $$$N$$$ shirts that look identical for a challenge. Among these shirts, $$$N - 1$$$ have exactly the same weight, while one different shirt is heavier than all the others.

You may use a two-pan balance scale. In each weighing, you choose the same number of shirts to place on the left pan and on the right pan. The scale tells whether the left pan was heavier, the right pan was heavier, or both pans had the same weight.

Your goal is to find which shirt is the heaviest using at most $$$8$$$ weighings.

Initially, the interactor prints a line containing an integer $$$N$$$ ($$$2 \leq N \leq 2000$$$), the number of shirts. The shirts are numbered from $$$1$$$ to $$$N$$$.

The interactor is non-adaptive: the heaviest shirt is chosen before the interaction starts and does not change during execution.

Your program may perform weighings. To perform a weighing, print a line in the format

where $$$t \geq 1$$$. The shirts $$$a_1, a_2, \ldots, a_t$$$ will be placed on the left pan, and the shirts $$$b_1, b_2, \ldots, b_t$$$ will be placed on the right pan. All these $$$2t$$$ indices must be distinct and between $$$1$$$ and $$$N$$$.

The interactor will answer with a line containing a single character:

• E, if the left pan was heavier;
• D, if the right pan was heavier;
• I, if both pans had the same weight.

When your program knows which shirt is the heaviest, it must print a line in the format

where $$$p$$$ is the index of the heaviest shirt.

The answer operation does not count as a weighing. Only operations that start with ? are counted, and your program may perform at most $$$8$$$ of them.

After printing any line, your program must flush the output. For example, in C++ you may use cout « endl; or cout.flush().

If your program prints an invalid value, performs more than $$$8$$$ weighings, or answers an incorrect shirt, it will receive the verdict NO - Wrong answer.

During his vacation in Aracaju, Samuell decided to spend the morning swimming at Atalaia Beach, one of the city's postcards, famous for its beautiful and long stretch of sand.

When it was time to leave, a problem came up: with the sun high in the sky, he must cross the entire beach, from the sea to the boardwalk, and request an Uber. To avoid getting sunburned, Samuell plans to use the shadows of the beach umbrellas spread across the sand and choose a route that minimizes the distance walked under the sun.

Formally, the beach can be represented by the strip between two parallel lines: one is the line where the sea meets the sand ($$$y = 0$$$), and the other is the boardwalk ($$$y = H$$$), at distance $$$H$$$ from the first one. There are $$$N$$$ beach umbrellas; the $$$i$$$-th one casts a circular shadow with center $$$(x_i, y_i)$$$ and radius $$$r_i$$$.

Assume Samuell can swim freely underwater without being exposed to the sun, and can leave the water at any point on the sea line. Once on the sand, he can:

• walk under the shadow of a beach umbrella, including moving directly to another one when their shadows touch or overlap;
• leave the sand at any point on the boardwalk.

Help Samuell determine the minimum distance he must walk under the sun to reach the boardwalk.

The grand final of the Tengo-lengo-tengo World Cup is about to begin! The decisive match will be played between Altos and Bahia, and the line to enter the stadium is pure chaos.

The line is made entirely of fans of the two teams. As tradition dictates, whenever an Altos fan is standing before (closer to the stadium entrance than) a Bahia fan, we say there is a banter happening between them.

Mathematically, if we view the line as a string $$$S$$$ made of the letters 'A' and 'B', a banter is formed by each pair of indices $$$(i, j)$$$ such that $$$i \lt j$$$, where $$$S[i]$$$ is an Altos fan ('A') and $$$S[j]$$$ is a Bahia fan ('B').

The stadium organization recorded $$$Q$$$ events in the line, which can be of $$$4$$$ types:

• Type 1: A fan of team $$$X$$$ ('A' or 'B') joins the end of the line.
• Type 2: A mischievous fan of team $$$X$$$ ('A' or 'B') cuts in at the exact front of the line.
• Type 3: The fan at the end of the line gets tired of waiting and leaves.
• Type 4: The fan at the front of the line goes through the turnstile and enters the stadium.

Your task is to compute the total number of banters happening in the line immediately after each event.

Since childhood, the cordel poet Severino has kept tales heard at countryside markets: singing duels, enchanted creatures, and brave deeds passed down through generations. Now he is preparing his greatest booklet, an adventure where, in each chapter, the reader chooses how the story continues. To avoid losing any ending, Severino spread the pages of his outline on the floor and connected each choice with a piece of string.

Seen from above, the outline resembles a tree structure: there are $$$N$$$ chapters numbered from $$$1$$$ to $$$N$$$, with chapter $$$1$$$ being the beginning of every story. The outline follows these rules:

• Each connection links a chapter to one of its immediate continuations;
• For each connection, Severino must choose an uppercase letter between A and Z;
• No chapter may have two continuations with the same letter;
• Each chapter with no continuations ends a complete story, described by the sequence of letters on the path from chapter $$$1$$$ to it.

Severino also noticed that changing letters in the outline does not always change the booklet: two assignments of letters are considered equivalent when they produce exactly the same set of complete stories.

Severino wants to know how many distinct sets of complete stories can be obtained from this outline among all possible assignments of letters. Since the answer can be very large, he asks you to report it modulo $$$998244353$$$.

XORlandia is a city on the coast of Northeastern Brazil, famous for its crystal-clear beaches, its enormous waterfront, and its slogan XORlandia is massa. Legend says that, during the construction of the city, an old fisherman known as Old Sururu cursed some of the region's streets after losing a dominoes match to a local resident.

Since then, each street in the city has had an energy, represented by an integer associated with it. The city has $$$N$$$ tourist spots numbered from $$$1$$$ to $$$N$$$; spot $$$1$$$ is Marco dos XORais and spot $$$N$$$ is where the XORgante Chair is located. They are connected by $$$M$$$ bidirectional streets. The $$$i$$$-th street connects spots $$$U_i$$$ and $$$V_i$$$ and has energy $$$W_i$$$. It is also known that it is possible to reach any spot from any other, and that there is at most one street connecting each pair of spots.

As a local tradition, residents define the value of a path as the XOR of the energies of all streets traversed. A path may pass through the same spot and traverse the same street multiple times. Each time a street is traversed, its energy is included again in the XOR calculation, even if that same street has already been used earlier in the path. The city hall considers XORlandia an incredible city if every path that starts at Marco dos XORais and ends at the XORgante Chair has value equal to $$$0$$$.

Therefore, the city hall decided that it may choose exactly one street and change its energy to any other non-negative integer value, as long as it is different from the previous value.

For each street, determine whether it is possible to change only the value of that street so that the city becomes incredible.

In this game, there is a sequence of $$$N$$$ cards placed at the center of a table. Each card has a distinct number from $$$1$$$ to $$$N$$$, so the sequence forms a permutation of these values. Each card represents a song in the repertoire, and the number written on it is that song's score, indicating how much the audience likes it.

The festival will have several performance days, and on each day they choose an interval of the sequence, indicating which songs will be available to sing that day. The game is then played considering only this contiguous interval of cards. The singers alternate turns, with Adilson always making the first move. On each turn, the current player must remove exactly one card from the remaining sequence: either the leftmost card or the rightmost card. The removed card represents a song that will be sung by that singer during the show.

Each singer's score is the largest number written among all cards they removed during the game, representing the song by that singer that excited the audience the most. If a singer does not remove any card, their score is $$$0$$$. When all cards have been removed, the singer with the larger score wins. Since all numbers in the sequence are distinct, there is always exactly one winner.

For each given interval, determine which singer wins assuming both play optimally.

João went to the São João festival in Caruaru with a simple mission, at least in his mind: buy sweets for his friends and still keep a little treat for himself to eat after the forró.

João has $$$A$$$ friends and found a stall selling exactly $$$X$$$ different types of sweets. He wants to choose a positive integer $$$Y$$$ and buy exactly $$$Y$$$ sweets of each type. Thus, in total, João would buy $$$X \cdot Y$$$ sweets.

After the purchase, João will distribute the sweets equally among his $$$A$$$ friends, possibly leaving some sweets over. Each friend must receive at least one sweet, because showing up at the party and leaving empty-handed is reason for jokes until the next São João.

To make the count come out exactly as he imagined, exactly one sweet must be left for João himself. Therefore, he wants to know whether there exists some value of $$$Y$$$ that allows this. If it exists, determine the smallest possible one.

Every four years, in Northeastern Brazil, the FFT (Tengo-lengo-tengo Football Federation) holds the Tengo-lengo-tengo World Cup. Because of the great importance of this competition, the fans soon affectionately nicknamed the tournament the Lampions League, in reference to that weaker European competition; after all, everyone knows the competitive level in the Tengo-lengo-tengo World Cup is high.

During the final match, the official announcer will narrate the plays in a special way. On the first play, he shouts Tengo $$$1$$$ time; on the second, he shouts Lengo $$$2$$$ times; on the third, he shouts Tengo $$$3$$$ times; on the fourth, he shouts Lengo $$$4$$$ times; and so on, alternating the word until play $$$N$$$.

The FFT needs to know whether the absolute difference between the number of times Tengo was shouted and the number of times Lengo was shouted is even or odd.

Given the value of $$$N$$$, determine whether this difference is even or odd.

Every year, one debate stirs Northeastern Brazil: after all, which is the world's biggest São João, the one in Campina Grande or the one in Caruaru?

To try to settle the matter, a research institute decided to run two polls: one during the São João festival in Campina Grande and another during the São João festival in Caruaru.

The $$$N$$$ interviewed people attended both festivals, experiencing both Campina Grande's São João and Caruaru's São João up close. However, for organizational reasons, each person took part in exactly one of the two polls.

It is allowed for one of the polls to be empty.

Each person has a true opinion about which festival they prefer: Campina Grande or Caruaru.

However, the polls happened in the middle of the party, with lots of forró, fireworks, and noise. Because of that, when a person said their answer, the institute could end up hearing it wrong. Thus, the vote recorded for a person may be different from their true opinion.

A few days later, each participant receives the result of the poll they joined: how many votes were recorded for Campina Grande and how many votes were recorded for Caruaru.

Each person's evaluation of the poll depends only on their true opinion:

• for each vote recorded for the festival they prefer, their evaluation increases by $$$1$$$;
• for each vote recorded for the other festival, their evaluation decreases by $$$1$$$.

The total score of a poll is the sum of the evaluations of all its participants.

Assuming each participant was assigned to a poll in a way that maximizes the sum of the scores, determine the largest possible sum of the scores of the two polls.

Xand Avião is very excited to start completing the new sticker album of the Tengo-lengo-tengo Football Federation (FFT). That is because the new FFT album works like bingo: on the day you complete it, you win a prize!

The album initially has $$$N (N \leq 2026)$$$ players licensed by the FFT. Each day, in the morning, there is a $$$P\%$$$ chance that a new player joins the album. This can only happen if there are fewer than $$$2026$$$ players in the album. After all, this is the total number of football players in the world!

Xand initially has no stickers. So every day, in the afternoon, Xand will buy a new one. The sticker is equally likely to be any player currently in the album. At that moment, if Xand has all stickers of the players that are already in the album, he immediately exchanges the album for his prize.

Xand is so excited about the prize that he can barely count the days until he completes the album. So he asked for your help to count for him: what is the expected number of days Xand will need to win the sticker album prize?

Viação Mandacaru runs a daily route through $$$M$$$ cities in Northeastern Brazil, numbered from $$$1$$$ to $$$M$$$ in the order in which they are visited. The bus used on this route has exactly $$$C$$$ seats.

One day, a system failure simultaneously interrupted $$$N$$$ ticket requests. Although no ticket was issued, the request data was recovered. Passenger $$$i$$$'s request is described by three integers $$$L_i$$$, $$$R_i$$$, and $$$P_i$$$: the passenger wants to board in city $$$L_i$$$, get off in city $$$R_i$$$, and would pay $$$P_i$$$ reais for the ticket.

The company does not allow passengers to choose their seats. Therefore, a request can only be accepted if the bus has an available seat during the entire trip between cities $$$L_i$$$ and $$$R_i$$$. In each city, all passengers whose trip ends there get off before new passengers board. Thus, a passenger boarding in city $$$j$$$ may occupy a seat freed in that same city.

Since all requests were received at the same time, it may be impossible to accept all of them without exceeding the bus capacity on some segment of the route. Always concerned with solving the situation as fairly as possible, especially for its own cash register, Viação Mandacaru decided to choose which tickets will be issued so as to maximize its revenue.

Determine the maximum total value the company can earn by issuing a subset of the requests, without the bus carrying more than $$$C$$$ passengers simultaneously on any segment of the trip.