Today is Gabriel's first day at his new job, and he has been given his first task. He needs to read a string made up of uppercase letters from a file, sort the letters in the string alphabetically, filter out repeated letters, and then write the result back to the original file. For instance, sorting the string "ICPC" would produce "CCIP", which would become "CIP" after removing repeated letters. Easy, right?

However, Gabriel made a tiny mistake. Instead of overwriting the file with the filtered string, he accidentally appended it to the file. Now, the file is corrupted, containing the original string followed by the sorted, duplicate-free version of it, and Gabriel is in a bit of a panic.

Given the content of the corrupted file, can you determine the length of the original string? Gabriel is confident that with this information, he will be able to complete his assigned task.

Biketopia is a country proud of its thriving bike culture. There are $$$N$$$ cities and $$$M$$$ two-way roads in the country. Each road is fully prepared for cyclists and connects a different pair of cities, in such a way that it is possible to travel between any two cities using one or more roads. Besides, each city is an endpoint of at least three roads.

With the annual bicycle racing tournament approaching, Biketopia needs to select a cyclic track along the roads to serve as the competition route. This track must form a closed loop of roads, passing through at least three distinct cities. While the track can pass through the same city multiple times, no road can be used more than once.

On race day, the roads selected for the track will be closed to the public, but the cities on the track will remain accessible. In past tournaments, some cities became unreachable due to road closures, causing significant disruptions. This is where your help is needed. Your task is to find a cyclic track such that, even after the track's roads are closed, it remains possible to travel between any two cities in the country.

As an example, consider the illustration above, which corresponds to the first sample. The roads highlighted with dotted lines ($$$14$$$, $$$9$$$ and $$$12$$$) indicate the chosen competition track. This track forms a closed loop, visiting three different cities ($$$4$$$, $$$7$$$ and $$$8$$$). Note that it remains possible to travel between any pair of cities using the remaining roads. Additionally, another possible track is shown with dashed lines, illustrating that the solution is not unique.

The Christmas season is approaching! The town of Who-ville is getting colorful again, and so are the houses of its citizens, the Whos.

Cindy Lou Who, a young girl living in the city, has a very peculiar Christmas tradition: Cindy goes through her neighborhood, door-to-door, asking for red and blue Christmas tree balls. She gathers all the balls she collects and arranges them in her backyard. This Christmas, Cindy collected $$$R$$$ red balls and $$$B$$$ blue balls, which she arranged in a sequence with all red balls first, followed by all blue balls. Cindy called this arrangement an $$$(R, B)$$$-sequence.

Near Who-ville lives Grinch, a cranky and solitary creature who hates Christmas and envies the Whos' holiday cheer. He sneaked into Cindy's backyard at night and replaced her $$$(R, B)$$$-sequence with an arbitrary sequence $$$S$$$ of red, blue, and green balls (which isn't a color Cindy likes, as it doesn't contrast well with Christmas trees).

The Whos, known for their cheerful Christmas spirit, immediately offered to help Cindy recover her $$$(R, B)$$$-sequence. Although she was initially mad at whoever messed in her backyard, she came up with an idea to turn this into a joyful Christmas game.

The game works as follows. For each citizen, Cindy will pick a contiguous subsequence, $$${S_L}, S_{L+1}, \ldots, {S_U}$$$, from Grinch's sequence and ask the citizen for the minimum number of operations needed to transform the subsequence into an $$$(R, B)$$$-sequence. An operation consists of adding, removing or replacing a ball at any position within the subsequence. Note that each subsequence is not actually transformed into an $$$(R, B)$$$-sequence; the citizen must just inform the minimum number of operations required.

Your task is to compute, for each Who, the minimum number of operations required for their assigned contiguous subsequence.

As an example, for $$$R=3$$$ and $$$B=2$$$, consider the picture above. At the top of the picture is Cindy's original $$$(3, 2)$$$-sequence (1). Below that is the sequence $$$S$$$ after Grinch's attack (2). A possible contiguous subsequence with $$$L=3$$$ and $$$U=5$$$ follows (3). Finally, a way to transform the subsequence into a $$$(3, 2)$$$-sequence using four operations is shown, replacing the first two balls with red balls and adding two blue balls at the end (4). Four is the minimum number of operations required for this contiguous subsequence.

The Innovative Clothing Pattern Championship (ICPC) is approaching, and the organizers are determined to ensure that the selection of contestants' T-shirts meets the competition's high standards of variety and style.

To achieve this, they are negotiating with a T-shirt vendor that offers $$$N$$$ distinct models. Each model is defined by a unique combination of a text color and a background color, and is assigned an integer from $$$1$$$ to $$$N$$$ to identify this combination.

To keep the selection visually diverse, the organizers have decided to follow a strict diversity rule: no two selected models can share the same text color or the same background color. For example, if one model has "red text on a blue background" and another has "red text on a white background", only one of them can be chosen because they share the same text color. Conversely, models like "white text on a black background" and "black text on a white background" do not share either the text or background color, so both may be chosen.

To assist the organizers, the vendor has prepared an $$$N \times N$$$ binary matrix $$$A$$$ that identifies all incompatible pairs of models. Specifically:

• $$$A_{i,j} = 1$$$ if $$$i \neq j$$$ and models $$$i$$$ and $$$j$$$ cannot both be chosen because they share either the text color or the background color, and
• $$$A_{i,j} = 0$$$ otherwise.

The organizers need your help to determine if it is possible to select enough T-shirt models for the event while respecting the diversity rule. Using the vendor's matrix, can you determine the maximum number of models that can be selected?

After an unforgettable trip through Nlogonia's scenic viewpoints, Lola and her husband are back to tackle their most ambitious adventure yet: the Evereth Expedition. This famous mountain has $$$N$$$ stations built at distinct altitudes, each offering breathtaking views and a chance to rest along the way. Stations are identified by integers from $$$1$$$ to $$$N$$$, ordered by altitude (from lowest to highest). Multiple trails connect the stations and the base of the mountain, ensuring it is safe to move between the base and any station, as well as between any pair of stations.

To make the most of their hike, Lola has carefully planned an itinerary that, starting from the base of the mountain, would take the couple through each station exactly once. Since going up and down multiple times would require extra effort, the itinerary consists of a single ascent to the peak and then a descent back to the base. However, just before Lola could double-check the itinerary for any mistakes, she accidentally spilled coffee on her notes, leaving some station numbers unreadable. Without time to plan it all over again, Lola needs your help.

Your task is to complete the itinerary by filling in the unreadable numbers, so that it is possible to visit each station exactly once, in a single ascent followed by a single descent. Note that it is also valid to visit all the stations on the way up or all on the way down.

You surely agree that the best place to use a restroom is at home. However, sometimes people have no choice but to use a public restroom, where toilets are often arranged side by side in a single row. Aiming for some privacy, each person who enters such restroom will choose an unoccupied toilet that has no occupied toilets on its sides.

Suppose that $$$K$$$ people arrive at a public restroom with $$$N$$$ initially unoccupied toilets arranged in a row. Determine if it's possible that each of the $$$K$$$ people chooses a toilet with no occupied toilets on its sides, and an additional person would not be able to find an unoccupied toilet meeting this privacy condition. People choose toilets one by one, and each chosen toilet is immediately occupied before the next person is allowed to choose.

The Kingdom of Arboria has developed a vast network of $$$N$$$ villages numbered from $$$1$$$ to $$$N$$$. These villages are interconnected by $$$N-1$$$ two-way roads, forming an unrooted tree.

These days, the kingdom's streets are buzzing with excitement over the upcoming Grand Glory Race. This prestigious race has been losing popularity in recent years. Over time, all the runners became so well-prepared that now they all run at the same speed. Because all runners move at the same pace, the order in which they reach each village is determined purely by the starting point, as each runner always takes a shortest path toward the finish line. Thus, it became easy to predict who would win the race, taking away much of the interest.

But this year, the race organizers have introduced some intriguing new rules to make the competition more engaging:

• The Crown Village is Still a Mystery: The race will conclude at the Crown Village, but no one knows yet which village it will be. The suspense is building with speculations, keeping everyone guessing and adding excitement to the event.
• The Racers: Each leaf village (a village with only one connecting road) will send one runner to participate. These runners will start from their respective leaf villages and race toward the Crown Village along a shortest path. Once a runner reaches the Crown Village, the race ends for them, but other runners continue their journey toward the Crown Village until they arrive.
• Claiming Villages: To make the race more appealing for every village, the first runner to reach a village claims it. If multiple runners arrive at a village at the same time, the runner starting from the leaf village with the smaller identifier claims the village. This way, even if a runner doesn't reach the Crown Village first, they can still claim more villages along the way, keeping the race competitive and unpredictable.

With these new rules in place, bookmakers across the kingdom are analyzing the odds for different runners. While the order in which the runners reach the Crown Village is easy to determine, what really interests the bookmakers is how many villages each runner can claim during their journey.

To assist the King's bookmaker, you are tasked with answering queries about various race scenarios. For each query, you'll be given two numbers: the identifiers of a leaf village $$$S$$$ and a village $$$T$$$, hypothetically chosen as the Crown Village. Based on this, you need to determine how many villages will be claimed by a runner starting at $$$S$$$ if the race ends at $$$T$$$.

Prometheus is a programmer. He wrote a large program in Heraclosures, a programming language invented by his friend Heracles. The program contains $$$N$$$ functions, each identified uniquely by an integer from $$$1$$$ to $$$N$$$. Each function is made up of many instructions, some of which are call instructions that invoke other functions.

When a call instruction in function $$$i$$$ calls a target function $$$j$$$, the full code of function $$$j$$$ is executed before continuing with the execution of function $$$i$$$. Each function may contain multiple call instructions, and it is possible for a function to call another function several times. Some functions, however, may have no call instructions at all. Following advice from his friend Sisyphus, Prometheus ensured that there are no cycles among the function calls, avoiding endless call loops.

Each function $$$i$$$ has a base execution time $$$B_i$$$, which is its execution time excluding any functions it calls. Execution times are measured in processor cycles, so $$$B_i$$$ is always a non-negative integer. The total execution time of function $$$i$$$, denoted as $$$T(i)$$$, includes both its base execution time and the total execution time of all functions it directly calls. Formally, $$$$$$T(i) = B_i + \sum_{j \in C(i)} T(j) \enspace ,$$$$$$ where $$$B_i$$$ is the base execution time we already defined, and $$$C(i)$$$ is the multiset of functions that function $$$i$$$ directly calls. If function $$$i$$$ calls function $$$j$$$ multiple times, then $$$T(j)$$$ appears multiple times in this sum. If function $$$i$$$ has no call instructions, then $$$C(i)$$$ is empty, and so $$$T(i) = B_i$$$.

Prometheus wants to assess the impact of several code adjustments on the performance of his program. Tired of programming, he has hired you to implement a tool that accepts a list of events, where each event is either an update or a query.

• An update sets $$$B_i$$$ to a given value $$$V$$$. Notice that while this event may modify the base execution time of function $$$i$$$, the multiset $$$C(i)$$$ of its called functions remains the same.
• A query calculates the current total execution time $$$T(i)$$$ of function $$$i$$$, taking into account all updates that have occurred up to that point in the event list.

As a first approach, Prometheus does not want the result of each query but a single summary result. Suppose there are $$$q$$$ queries, numbered sequentially from $$$1$$$ to $$$q$$$ in the list of events. Then, the summary result is calculated as: $$$$$$ \left( \sum_{k=1}^q k \cdot T(i_k) \right) \bmod (10^9 + 7) \enspace , $$$$$$ where $$$T(i_k)$$$ is the total execution time of the function specified in the $$$k$$$-th query, taking into account all updates up to that query.

In MathemIsland, the wildlife is very diverse. There are roots, trees, leaves, pigeons – everything you'd find in a math book. And everywhere you look, there is a permutation.

ICPC University has devised a systematic way to catalog these permutations. Specifically, because inversions are of utmost importance in studying wildlife genetics, ICPC University has decided to sort all $$$N!$$$ permutations of the integers from $$$1$$$ to $$$N$$$: first by the number of inversions and, in the case of a tie, by lexicographic order. This approach uniquely identifies each permutation by an integer from $$$1$$$ to $$$N!$$$, indicating its position in the sorted list of all $$$N!$$$ permutations.

Thus, the identity permutation ($$${1}, {2}, \ldots, {N}$$$), which is the only permutation with zero inversions, is assigned the identifier $$$1$$$, while the reverse identity permutation ($$${N}, {N-1}, \ldots, {1}$$$), which is the only one with the maximum number of inversions, is assigned the identifier $$$N!$$$.

As part of the team implementing the ICPC University database, your task is to retrieve a specific permutation based on its identifier. Write a program that, given two integers $$$N$$$ and $$$K$$$, outputs the permutation of the integers from $$$1$$$ to $$$N$$$ corresponding to identifier $$$K$$$.

Remember that the number of inversions in a permutation is the number of pairs of elements that are out of their natural order. That is, for a permutation $$$\pi$$$ with $$$N$$$ elements, its number of inversions $$$\mathop{\mathrm{inv}}(\pi)$$$ is defined as $$$$$$\mathop{\mathrm{inv}}(\pi) = \left| \{ (i, j) : 1 \leq i \lt j \leq N \land \pi(i) \gt \pi(j) \} \right| \enspace$$$$$$

They finally did it! The flat-earthers managed to teleport themselves to an idealized flat world where no one can make fun of them anymore.

In this world, there is a perfectly straight, infinite road that runs along the $$$x$$$-axis. Instead of a sun, they have something more illuminating: a gigantic flashlight elevated above the road, positioned infinitely far away to the west (negative $$$x$$$-axis). This flashlight beams light at a precise angle with respect to the ground, illuminating the entire road.

There are $$$N$$$ flatlanders standing proudly at distinct positions along the road. As the light strikes each of them, it casts a shadow extending eastward (toward the positive $$$x$$$-axis).

Eager to show off their flat-world knowledge, the citizens want to calculate how much of the road is covered by their shadows. However, with shadows potentially overlapping, they need your help to figure it out. Given the positions of the flatlanders and their heights, can you calculate the total length of the road covered by their shadows?

Professor Kardashi is known for always being fashionable and for her passion for computer science. Her current obsessions are binary strings and efficiency. In particular, she says that a binary string is kool if it does not contain $$$K$$$ or more consecutive identical characters.

To test your skills, Professor Kardashi gives you a binary string $$$S$$$ and allows you to perform the following operation on it: choose an index $$$i$$$ and flip the value of $$$S_i$$$ (changing a '0' to '1' or a '1' to '0').

Your task is to transform $$$S$$$ into a kool string using the minimum number of operations.

A Latin square of size $$$N$$$ is an $$$N \times N$$$ matrix where each entry is an integer between $$$1$$$ and $$$N$$$, and no two entries in the same row or column are equal.

Alice has a Latin square of size $$$N$$$, and she applied a list of transformations to it. Each transformation swaps either two distinct rows or two distinct columns of the matrix. The transformations are applied sequentially: the first transformation is applied to the original matrix, the second to the result of the first transformation, and so on. The final result is, of course, an $$$N \times N$$$ matrix.

Alice will not reveal any matrix to you, only the list of transformations. Your task is to determine whether there exists an original matrix that, after applying all transformations, is identical to the final matrix. If such a matrix exists, you must also provide a possible content for this original matrix.