A meteor shower is about to happen! As the enthusiastic astronomy photographer that you are, you want to take a single picture of all the meteors that will be part of the phenomenon. Not only that, you want to take the best possible picture. You know that the smaller the area of the photo, the better the picture. But how small can you make the picture to capture them all?

You can take a picture of any rectangular region of your camera's view, but you cannot rotate the camera. That is, your photo can be any axis-aligned rectangle. The challenge? The meteors are constantly moving. Think of time ($$$t$$$) as the number of seconds that have passed since the start of the meteor shower. Your goal is to find a non-negative value of $$$t$$$ at which you can capture every single meteor with the smallest possible rectangle. A photo captures all the meteors within the rectangle, including those on the border.

Speedy Greedy is a professional speedrunner: they play a videogame repeatedly, with the aim of finishing it as quickly as possible.

The game that Speedy Greedy is currently tackling consists of $$$N$$$ levels, numbered sequentially from $$$1$$$ to $$$N$$$. Although these levels must be completed in order, each of them is independent of the others in terms of gameplay. That is, no event from one level can have a relevant effect on the next levels (unlike other games where items, spells, points, lives, etc. are carried over from one level to the next).

The current world record for the fastest completion time of the game is $$$T$$$ seconds. Speedy Greedy is determined to beat this world record, with no concern for the margin. Whether the game is finished $$$1$$$ second or $$$1000$$$ seconds faster than the current record is irrelevant: what matters to Speedy Greedy is improving the world record.

Speedrunners often choose and adjust their actions dynamically during a run, depending on various factors such as the situation of their character in the game. It is also common to restart the game, as for example once $$$T$$$ seconds have passed there is no more hope to beat the world record. Any run of the game can be restarted at any point. When a restart command is issued by the speedrunner, the game instantly restarts from the beginning. Thus, to beat the world record, Speedy Greedy must complete the $$$N$$$ levels sequentially, in a single run that takes less than $$$T$$$ seconds.

How can Speedy Greedy achieve that? Well, most sections of the game are completely safe and easy to play for a speedrunner of such skill. Those sections take fixed amounts of time and have no risk of failing. However, there is a very hard section in each of the $$$N$$$ levels, where the result of playing that section is not completely under Speedy Greedy's control, and also depends on the chosen strategy.

In each level, there are two possible strategies, and when reaching the hard section, Speedy Greedy can choose exactly one of them to attempt. Each strategy has its own probability of success, and the actual time that the level takes to complete depends on the chosen strategy and whether the attempt is successful or not.

For the purposes of this problem, we assume that Speedy Greedy can instantly detect whether the chosen strategy for a level succeeded or failed, right at the moment that the hard section of the level is reached. That is, reaching the hard section of a level, choosing a strategy, and knowing whether the attempted strategy succeeded or failed are all simultaneous events, occurring at exactly the same time.

Grinding the game by playing again and again and again becomes tiring and physically exhausting at such a high level of speedrunning competition. Speedy Greedy then decided to play the game so as to minimize the expected total play time until beating the world record. Your task is to compute this minimum.

Note that the total play time not only includes the time of the final successful run that takes less than $$$T$$$ seconds (beating the world record), but also includes the time spent during all previous failed runs.

Two players play the following game on an $$$N \times M$$$ grid:

• Initially, each cell of the grid is either empty or occupied.
• Players take turns placing a stone on an empty cell, occupying the cell. Each new stone must be adjacent to the last placed stone, with the exception of the starting stone that can be placed on any empty cell. A stone is adjacent to another stone if they are located in two cells that share a side.
• The game ends whenever a player cannot place a stone according to the above rules. In that case, the player who cannot place a stone loses the game, and the other player wins.

A winning starting cell is a cell such that the first player wins the game if they place their starting stone there, assuming both players play optimally. Given a description of the initial grid, you must tell how many winning starting cells it has.

The Intense Challenges Players Club (ICPC) is hosting a DiviDuelo tournament.

DiviDuelo is a new two-player, turn-based game. In DiviDuelo, a number $$$N$$$ is selected and the list of its divisors is written. For example, if $$$N=10$$$ is selected, the list of numbers $$$1, 2, 5, 10$$$ is written. Players alternate turns picking one still unpicked divisor from the list each turn, until all divisors have been picked.

The winner is determined by the greatest common divisor (GCD) of the numbers picked by the starting player. If the GCD is not equal to $$$1$$$, the starting player wins. Otherwise, if the GCD is equal to $$$1$$$, the other player wins.

The ICPC needs your help to prepare some statistics about the games played in the tournament. Given the value of $$$N$$$, determine if the starting player can win the game assuming both players play optimally.

Tired of always waiting in lines, you invented a revolutionary restaurant concept: "STACKS! Where the last customer is served first".

The restaurant operates as follows:

• There is a single line inside the restaurant.
• When a customer enters, they immediately join the back of the line.
• Whenever a stack of glazed pancakes (the only dish at STACKS!) is ready, it's served to the person at the back of the line, who then immediately devours the pancakes and leaves the restaurant.

In fact, you just opened the very first STACKS!+, offering two types of pancakes: glazed and savory. The new restaurant works as follows:

• There are two lines, one for each type of pancake. Each customer joins the back of the line corresponding to the type of pancake they want.
• Whenever a stack of glazed pancakes is ready, it is served to the customer at the back of the glazed pancake line, who immediately devours it and leaves the restaurant.
• Whenever a stack of savory pancakes is ready, it is served to the customer at the back of the savory pancake line, who instantly gobbles it and leaves the restaurant.

As the boss, you want to ensure your employees follow the concept and maintain your vision. Given the order in which customers come in and out of the restaurant, you need to determine whether there is an assignment of customers to lines such that the STACKS!+ concept is followed.

You can assume that whenever a customer enters the restaurant, they immediately join the back of a line, and that they leave as soon as they are served. Also, each customer visits the restaurant exactly once.

An entrepreneur has $$$N$$$ blueprints, each describing a type of building. Each blueprint specifies the building's height through two integers $$$G$$$ and $$$R$$$.

• $$$G$$$: Height of the ground floor. It can be zero, indicating that the building has no ground floor.
• $$$R$$$: Height of each residential floor. Each building has at least one residential floor.

The entrepreneur wants to distribute all of these blueprints among their two children Alice and Bob. Each child will build exactly one building from each blueprint allocated to them, choosing the number of residential floors for each building.

The entrepreneur wants to avoid showing favoritism towards either child, so they are looking for a fair distribution of the blueprints. They decided that a fair distribution is one in which it is possible to construct the buildings in such a way that the sum of the heights of the buildings constructed by each child is the same. Can you tell whether a fair distribution exists?

Consider the following example for $$$N=3$$$ blueprints:

1. $$$G = 1$$$ and $$$R = 1$$$ (possible heights are $$$2, 3, 4, \ldots$$$);
2. $$$G = 0$$$ and $$$R = 3$$$ (no ground floor, possible heights are $$$3, 6, 9, \ldots$$$);
3. $$$G = 2$$$ and $$$R = 1$$$ (possible heights are $$$3, 4, 5, \ldots$$$).

Since the early civilizations, humankind has enjoyed games of chance. Even the ingenious Greeks, known for their groundbreaking concept of the least common multiple (LCM), couldn't resist a good gamble.

Inspired by this mathematical marvel, folks in Athens devised a unique betting system: after purchasing a ticket, a participant would receive a random number of coins. To determine this number, there are $$$N \ge 3$$$ ordered slots numbered from $$$1$$$ to $$$N$$$. A token is initially placed at slot $$$1$$$, and the following steps are repeated:

• Let $$$x$$$ be the number of the slot where the token is currently located.
• Generate a random integer $$$y$$$ between $$$1$$$ and $$$N$$$, and compute $$$z$$$, the LCM of $$$x$$$ and $$$y$$$.
• If $$$z \gt N$$$, the procedure ends.
• Otherwise, the token is moved to slot $$$z$$$, and the participant receives one coin.

As it is well known, the house always wins: the casino employs a particular probability distribution for generating random integers, so as to ensure a profitable outcome.

The casino owner is constantly seeking to optimize the betting system's profitability. You, an AI designed to aid in such tasks, are given $$$N$$$ and the probability distribution. Determine the expected total number of coins awarded to a participant.

In this problem, we consider three types of operations that can be applied to any $$$0$$$-based string $$$t$$$ of length $$$|t| \geq 2$$$.

• $$$I(t)$$$: Reverses $$$t$$$.
• $$$R(t,D)$$$: Rotates $$$t$$$ to the right $$$D$$$ positions, for some positive integer $$$D \lt |t|$$$. That is, for each $$$0 \leq i \lt |t|$$$, the character at position $$$(i + D) \bmod |t|$$$ in $$$R(t,D)$$$ is the character at position $$$i$$$ in $$$t$$$.
• $$$L(t,D)$$$: Analogous to $$$R(t,D)$$$, but rotates $$$t$$$ to the left instead of to the right.

When a list of the above operations is applied to a string, it is done sequentially in list order. That is, the first operation of the list is applied to the original string, the second operation is applied to the result after having applied the first operation, the third operation is applied to the result after having applied the first two operations, and so on.

You are given a string $$$S$$$ consisting of lowercase letters, and a list of $$$K$$$ operations $$${F_1}, {F_2}, \ldots, {F_K}$$$. Your task is to find out how many pairs of indices $$$(i,j)$$$ there are such that $$$1 \leq i \leq j \leq K$$$, and applying the sublist of operations $$${F_i}, {F_{i+1}}, \ldots, {F_j}$$$ to $$$S$$$ yields $$$S$$$ as the final result.

Consider, for instance, $$$S="\texttt{pda}"$$$, $$$K=2$$$, $$$F_1=R(t,2)$$$ and $$$F_2=L(t,2)$$$. The result of applying the sublist $$$F_1$$$ to $$$S$$$ is $$$R("\texttt{pda}",2)="\texttt{dap}"$$$, which is different from $$$S$$$. The result of applying the sublist $$$F_1, F_2$$$ to $$$S$$$ is $$$L(R("\texttt{pda}",2),2)=L("\texttt{dap}",2)="\texttt{pda}"=S$$$. Finally, the result of applying the sublist $$$F_2$$$ to $$$S$$$ is $$$L("\texttt{pda}",2)="\texttt{apd}"$$$, which is different from $$$S$$$. Thus, in this example, the answer is $$$1$$$.

Bog has three passions in life: insects, mathematics, accuracy, and efficiency. His last passion led him to wanting to merge the first two, so Bog decided to adopt a differential grasshopper, an adorable little green guy that he named Dydx.

In order to keep Dydx happy, Bog made him a little lair. He bought a sprinkler that could water any plant within a circle with radius $$$R$$$, and planted $$$N$$$ crops within this circle.

Dydx really liked his new home! But Bog realized that the grasshopper would only stay within the area defined by the smallest convex polygon that encloses all crops. Now he regrets not having spread the crops out more. Fortunately, Bog managed to find one last crop he hadn't planted yet. Bog wants your help to maximize the area Dydx can inhabit by planting his last crop within the sprinkler's range.

Apolyanka and Büdelsdorf are two small Neolithic villages that have recently come into contact. There are $$$N$$$ resources, numbered from $$$1$$$ to $$$N$$$, and each village is capable of independently producing any of them, albeit with different efficiencies. In order to produce one unit of resource $$$i$$$, Apolyanka needs $$$A_i$$$ person-hours, while Büdelsdorf needs $$$B_i$$$ person-hours. Currently, Apolyanka is producing $$$U_i$$$ units of resource $$$i$$$ in each given time period, while Büdelsdorf is producing $$$W_i$$$ units.

Each village is currently working at maximum capacity, that is, there is no way they can put more person-hours to work than they are employing now. However, through the recently discovered benefits of trade, it is possible for both villages to produce all the resources they need while reducing the total person-hours worked, and thus becoming able to spend those freed person-hours resting and playing some games. All that is needed is that the villages cooperate, coordinate work, and exchange resources among them.

For example, suppose $$$N = 2$$$, resource $$$1$$$ is wood, resource $$$2$$$ is food, $$$A_1 = 1$$$, $$$U_1 = 2$$$, $$$B_1 = 4$$$, $$$W_1 = 1$$$, $$$A_2 = 2$$$, $$$U_2 = 1$$$, $$$B_2 = 3$$$, and $$$W_2 = 4$$$. Then Apolyanka is doing $$$4$$$ person-hours of work: $$${A_1 \cdot U_1=}2$$$ for producing $$${U_1=}2$$$ units of wood, and $$${A_2 \cdot U_2=}2$$$ for producing $$${U_2=}1$$$ unit of food. Similarly, Büdelsdorf is doing $$$16$$$ person-hours of work: $$${B_1 \cdot W_1=}4$$$ for producing $$${W_1=}1$$$ unit of wood, and $$${B_2 \cdot W_2=}12$$$ for producing $$${W_2=}4$$$ units of food. Thus, the total production is $$${U_1+W_1=}3$$$ units of wood and $$${U_2+W_2=}5$$$ units of food, requiring $$$4+16=20$$$ person-hours.

However, a better organization is possible: Apolyanka could produce $$$3$$$ units of wood and $$$0.5$$$ units of food, while Büdelsdorf could produce no wood and $$$4.5$$$ units of food. The total production of each resource would be the same, but requiring only $$${3 A_1 + 0.5 A_2 + 0 B_1 + 4.5 B_2 =}3 + 1 + 13.5 = 17.5$$$ person-hours.

Another example with $$$N =3$$$ is $$$A_1 = 1$$$, $$$B_1 = 2$$$, $$$A_2 = 2$$$, $$$B_2 = 1$$$, $$$A_3 = 1$$$, $$$B_3 = 1$$$, and $$$U_i = W_i = 1$$$ for $$$i=1,2,3$$$. In this case, each village is currently working $$$4$$$ person-hours. With a slight reorganization, however, they can each work $$$3$$$ person-hours while producing the exact same total resources! All that is required is for Apolyanka to produce one less unit of resource $$$2$$$ and one more of resource $$$1$$$, while Büdelsdorf does the opposite.

Given all of these values, can you compute what is the minimum total number of person-hours that the villages have to work, in order to produce exactly the same total resources? Note that the number of person-hours invested in producing a resource is not required to be an integer.

You probably know the KMP algorithm. You may also know that "KMP" is an acronym that stands for "Knuth Morris Pratt", who jointly published the algorithm in 1977. How do you pronounce "KMP"? Of course, you can just say "Knuth Morris Pratt", but what about pronouncing the acronym itself? Since "KMP" is not a pronounceable word, you are forced to say the letters one by one. In this problem we are interested in pronounceable acronyms.

We need a few definitions to formalize the requirement. A phrase is a list of words and a word is a sequence of letters. Each letter is either a vowel or a consonant. Deciding whether a letter is a vowel or a consonant depends on the language and other elements. For simplicity, we say that the six letters "A", "E", "I", "O", "U" and "Y" are vowels, while all the rest are consonants. Although it is debatable whether a given word is pronounceable, we say that a word is pronounceable when it does not contain more than two contiguous consonants. For instance, "LEMPEL" is a pronounceable word, while "DIJKSTRA" is not.

Given a phrase composed of $$$N$$$ words, an acronym for the phrase is the concatenation of $$$N$$$ prefixes, one prefix for each word, in the order they appear in the phrase. Each prefix must have at least one and at most three letters. Your task is to determine the minimum length a pronounceable acronym can have.

As an example with $$$N=3$$$ consider the phrase "KNUTH MORRIS PRATT". There are $$$27$$$ possible acronyms for this phrase, such as "KMP", "KMPR", "KMPRA", "KMOP", "KMOPR" and "KNUMORPRA", among others. Some of these acronyms are pronounceable ("KMOP" and "KMOPR"), while some others not ("KMP", "KMPR", "KMPRA" and "KNUMORPRA"). Since the only three-letter acronym "KMP" is not pronounceable, it follows that "KMOP" is a minimum-length pronounceable acronym for the phrase.

An LED matrix is a two-dimensional array of LEDs that is used to display information. This is achieved by turning on the LEDs that form a desired pattern. The figure below represents an LED matrix displaying a smiling-face pattern. LEDs that are turned off are shown in white, while LEDs that are turned on appear colored.

Some LED matrices scroll the pattern from right to left across the matrix, turning on just the appropriate LEDs at each step. Thus, any pattern with the same height as the matrix can be displayed, even patterns that are wider than the matrix. The pattern scrolling works as follows: Initially, all the LEDs in the matrix are turned off. At the next step, the last column of the matrix displays the first column of the pattern. At each new step, the pattern is moved one column to the left across the matrix, until the first column of the matrix displays the last column of the pattern. Finally, all the LEDs in the matrix are turned off again. If an LED matrix is equipped with pattern scrolling, the scrolling occurs even if the pattern is not wider than the matrix.

The picture below shows all the steps required to display a pattern of an arrow that is pointing to the left.

Astrid has just received an old LED matrix with pattern scrolling, and she thinks that some LEDs might be broken. Since broken LEDs cannot be turned on, she is worried that some patterns will not display properly. Given the description of the state of each LED, and the pattern to display, you must tell whether the appropriate LEDs can be turned on at every step of the pattern scrolling.