There are $$$N$$$ ants on a circle. The circle has $$$L$$$ spot s numbered from $$$1$$$ to $$$L$$$ clockwise, with spot $$$L$$$ adjacent to spot $$$1$$$. Ants start at different spot s, and want to reach different spot s. To do so, in one second each ant may stay still or move around the circle to an adjacent spot (clockwise or counterclockwise).

No two ants can be at the same position on the circle at the same time, even between spot s. For instance, suppose that during a second an ant moves clockwise from spot $$$1$$$ to spot $$$2$$$. During that second, other ants cannot do any of the following:

• Stay still at spot $$$2$$$ (ants would meet at spot $$$2$$$).
• Move counterclockwise from spot $$$3$$$ to spot $$$2$$$ (ants would meet at spot $$$2$$$).
• Move counterclockwise from spot $$$2$$$ to spot $$$1$$$ (ants would meet between spot s $$$1$$$ and $$$2$$$).

Determine whether it is possible for all ants to reach their targets, and if so, the minimum number of seconds required. That is, find the minimum $$$t$$$ such that after $$$t$$$ seconds, every ant can be at its target spot.

Beatriz always enjoyed reading, so she decided to open a bookstore to have books around her all day long. She wants to be sure that the books are properly organized, so she can attract many customers.

On a large shelf of the bookstore there are $$$N$$$ stacks of books in a row, with the stacks numbered from $$$1$$$ to $$$N$$$ left to right. Stack $$$i$$$ contains $$$A_i$$$ books. Beatriz would like the numbers of books to be in non-decreasing order, that is, $$$A_i \le A_{i+1}$$$ for $$${i}={1}, {2}, \ldots, {N-1}$$$, which might require some rearrangement of the books.

However, Beatriz is lazy and she really does not feel like organizing the books by herself. Then she asked her best friend Bernardo for help. They agreed that Beatriz will give Bernardo a sequence of commands. In each command Beatriz will specify two distinct stacks $$$i$$$ and $$$j$$$, and Bernardo will take the $$$s = A_i + A_j$$$ books in those stacks, rearranging them as evenly as possible. This means that after performing the command, the number of books in those stacks will be updated in the following way: $$$$$$ A_i = \left\lfloor \frac{s}{2} \right\rfloor, \qquad A_j = \left\lceil \frac{s}{2} \right\rceil. $$$$$$

Beatriz does not want to spend a lot of time with Bernardo moving around the books for her. She wants a sequence of at most $$$10^{5}$$$ commands that yields the desired non-decreasing order. But, you know, Beatriz does not want to decide the commands by herself. Can you prepare any valid sequence of commands for her?

After a series of unfortunate events, dubious investments, and catastrophically failed marriages, Camila has decided to leave Earth for good. She does not have enough money to build a rocket, so her best hope is to be abducted by aliens. Camila asked an AI chatbot about it, and then she independently came to the conclusion that the best way to be abducted by aliens is by making a circle of crops.

The good news is that among Camila's poor investments there is a very large farm, which can be represented as the 2D plane. There are $$$N$$$ sprinklers located on the farm, and each of them waters all plants within a radius that depends on its power. Camila's plan is to plant corn seeds in a perfect circle. Since the soil of the farm is very dry, the whole perimeter of Camila's circle must be watered by some sprinkler. Notice that Camila only needs to water the perimeter of the circle, while areas inside of it may remain dry.

To maximize her abduction chances, Camila's circle needs to be as large as possible. Since you are one of her few remaining friends, she asks for your help to determine what is the largest circle of corn she can plant on her farm, given the position and radius of each sprinkler.

Drew P. Shipper received $$$N$$$ customer requests for products sold at a store called EvenBuy, where all product prices are even integers. To fulfill the $$$i$$$-th request, Drew must purchase a specific product that costs $$$A_i$$$ at EvenBuy, and Drew has already charged this price to the customer.

Drew is doing this for profit, based on a loyalty program that EvenBuy has: after Drew makes $$$X$$$ full-price purchases, he gets a discount of 50% in his next single purchase. This discounted purchase does not count toward the $$$X$$$ full-price purchases required to earn the next discount. Because Drew's customers paid him the full price upfront, he keeps the amount of the discount as his own profit whenever he purchases a discounted item.

Drew can decide the order of his purchases at EvenBuy to maximize his total profit. However, delivery times are directly related to the order of the purchases, and to avoid customer complaints, he cannot delay a purchase too much. In practice, Drew must fulfill the $$$i$$$-th request within his first $$$i + K$$$ purchases at EvenBuy.

Your task is to find the maximum total profit Drew can achieve. Each purchase fulfills exactly one request and each request must be fulfilled exactly once.

During the warmup session of Programadores de América (PDA) in Santiago de Chile, Ezequiel notices something alarming: the scoreboard looks blurry. Worried that the same thing might happen during the actual contest, he decides to quickly take an eye exam.

The optometrist runs a series of tests to find Ezequiel's true prescription, which is an integer $$$x$$$. Unfortunately, instead of carefully narrowing down the prescription, the optometrist uses the lenses in no particular order. Thus, in each test Ezequiel is shown two lenses with different correction degrees $$$A$$$ and $$$B$$$ ($$$A \lt B$$$), and he must tell his opinion about which lens is better. For each test Ezequiel answers:

• "A" if he thinks that $$$A$$$ is strictly closer to $$$x$$$ than $$$B$$$.
• "B" if he thinks that $$$B$$$ is strictly closer to $$$x$$$ than $$$A$$$.
• "E" if he thinks that $$$A$$$ and $$$B$$$ are equally close to $$$x$$$.

After running the tests in such a strange way, the optometrist does not know what to do with Ezequiel's answers, so they need your help. Given the results of all tests, you must determine the minimum and maximum integer prescriptions that are consistent with the tests. If no integer prescription is consistent with the tests, you must report it.

Antonella has $$$N$$$ colored balls, and she wants to build a stable pile of balls with them. For a pile to be stable, every ball must either lie on the ground, or be placed exactly on top of two other balls. Also, balls lying on the ground must be tightly packed, which means that there should be no empty space between them. The picture below shows three arrangements of balls; the one on the left is a stable pile, while the other two are failed attempts.

Antonella wants to build her stable pile in an incremental process. First, she will pick a ball and place it on the ground, forming a stable pile made of a single ball. Then, she will add the other $$$N-1$$$ balls to the pile, one at a time, keeping the pile stable at every step. If there are multiple places where Antonella could add a ball, she will choose the highest place (relative to the ground). If there are still multiple options, she can choose any of them.

A set of balls in a stable pile is considered connected if, for any two balls $$$s$$$ and $$$t$$$ in the set, there is a sequence of balls $$$s={b_0}, {b_1}, \ldots, {b_k}=t$$$ such that $$$b_{i-1}$$$ touches $$$b_i$$$ for $$${i}={1}, {2}, \ldots, {k}$$$. A cluster is a connected set of balls of the same color. The size of a cluster is the number of balls in it. The stable pile in the picture above has two red clusters of sizes $$$3$$$ and $$$1$$$, a green cluster of size $$$3$$$, and a blue cluster of size $$$6$$$. Given the colors of the balls in the order in which Antonella will use them, you must tell the maximum size among all clusters of all possible stable pile s that she can build.

A DNA sequence is a molecular chain composed of the four nucleobases: cytosine (C), guanine (G), adenine (A), and thymine (T). Those letters can be used to encode a genetic sequence as text.

Previously, we hypothesized that felines owe their traits to what we call their CAT degree. It's the number of times that their genetic sequence contains the nucleobases C-A-T in that order, ignoring other nucleobases between them. For instance, the sequences "GACT", "GCAT", and "CCGAAGT" have CAT degrees $$$0$$$, $$$1$$$, and $$$4$$$, respectively.

It turns out that was only half the picture. Researchers from Latin America were surprised to find healthy cats with below-average CAT degrees. Upon further study, they determined that there is a second factor regulating feline traits, now known as GATA degree. Similar to CAT degree, it's the number of times that a genetic sequence contains the nucleobases G-A-T-A in that order, ignoring other nucleobases between them.

Today you'll be crafting fresh DNA sequences in the lab. We will ask you for short genetic sequences (at most $$$500$$$ nucleobases) having specific GATA and CAT degrees. Please write a program to assist in our research.

Path-Digging Animals (PDA) is a new cooperative game for two players that is gaining popularity among programmers. The game is played on a board having $$$N$$$ holes and $$$N-1$$$ bidirectional tunnels. The tunnels form an undirected tree, which means that there is a unique simple path between each pair of holes.

A route in PDA is a simple path between two different holes. Since tunnels are bidirectional, the direction of a route is not relevant: the (unique) route from hole $$$U$$$ to hole $$$V$$$ and the (unique) route from hole $$$V$$$ to hole $$$U$$$ are the same route.

Players use animal-shaped pieces for playing PDA@. In each round of the game, each player independently chooses a route which is traversed by their animal, and both players score as many points as the number of tunnels that their route s have in common.

Right now Alicia and Bruno are at a board game party in Chile playing PDA, and they want to analyze their scoring possibilities. They would like to know, for each integer $$$k$$$ from $$$1$$$ to $$$N-1$$$, how many ordered pairs of route s $$$(A,B)$$$ there are such that Alicia and Bruno score exactly $$$k$$$ points if Alicia chooses route $$$A$$$ and Bruno chooses route $$$B$$$.

Evelyn and Todd play a game with a multiset $$$S$$$ of integers, and an array $$$v$$$ which is initially empty. After deciding who plays first, they take turns alternately. In each turn, the corresponding player chooses any element of $$$S$$$, appends it to the end of $$$v$$$, and removes it from $$$S$$$.

The game ends as soon as $$$S$$$ is empty. At that moment, the number of inversions in $$$v$$$ is counted, that is, the number of pairs of indices $$$i \lt j$$$ such that $$$v_i \gt v_j$$$. If there are an even number of inversions then Evelyn is the winner, while Todd wins if the number of inversions is odd.

Evelyn and Todd have been playing the game for quite some time, and now both play optimally. Thus, for a given multiset $$$S$$$, there are four possible outcomes:

• Evelyn wins, regardless of who plays first.
• Todd wins, regardless of who plays first.
• The first player wins, regardless of who they are.
• The second player wins, regardless of who they are.

Churro, a chubby and energetic guinea pig, has just started a new job at a fancy restaurant called Jaime's Palace. Since she is the newest employee, she is only responsible for washing and arranging the plates. Churro discovered that the most efficient way to keep the plates organized and easily accessible for the chef is by storing them in a single stack.

There are $$$P$$$ plates in Jaime's Palace, and $$$K_i$$$ of them are used on the $$$i$$$-th day. Churro designed a rigid and highly logical system for managing the plates. On the $$$i$$$-th day she takes the top $$$K_i$$$ plates from the stack and the chef uses each of them just once during the day. At the end of the day, Churro washes the $$$K_i$$$ used plates and places them back on top of the stack in an arbitrary order.

Churro's system is a real success. However, she is curious about the following questions. After repeating the above procedure for $$$D$$$ days, can she be sure that there is a plate that was used at least $$$t$$$ times? What is the maximum value of $$$t$$$ that she can guarantee? Please help Churro to determine that value.

Catarina loves all cats that live in her neighborhood. Her lifelong dream is to design a large cat-seeing circuit, so that every day she can go out and greet the cats while doing some exercise.

Catarina's neighborhood can be represented as the 2D plane, with the North-South direction aligned with the $$$y$$$-axis. A cat-seeing circuit that visits $$$m$$$ cats consists of exactly $$$m$$$ steps. Catarina chooses a starting position $$$(x_0, y_0)$$$ and faces one of the four cardinal directions. For each step $$${i}={1}, {2}, \ldots, {m}$$$ the following occurs:

• Catarina chooses a value $$$k_i \gt 0$$$ and walks $$$k_i$$$ units from $$$(x_{i-1}, y_{i-1})$$$ straight ahead in her current direction, stopping at the location of a cat that she has not greeted during any previous step.
• Catarina greets the cat, taking some time to appreciate its beauty.
• Without turning around, Catarina walks another $$$k_i$$$ units straight ahead in her current direction, stopping at a position $$$(x_i, y_i)$$$.
• Catarina turns $$$90^\circ$$$ either clockwise or counterclockwise, facing again one of the four cardinal directions.

Catarina knows the location of the $$$N$$$ cats that live in her neighborhood. Surprisingly, no two cats have the same $$$x$$$-coordinate or the same $$$y$$$-coordinate. Your task is to determine the maximum length that a cat-seeing circuit can have.

Nathan is running late to the annual meeting of the Public Disobedience Association (PDA). He was driving there as fast as he could until he got stuck in front of a red light. As he is in a hurry, he wants to cross the street anyway (see Disclaimer). Of course, Nathan is not a monster, so he will cross the street only if there is enough space to cross it without hurting any pedestrian. At a given time $$$T$$$, Nathan has the "feeling" that he could cross the street safely, but Nathan's feelings can be completely wrong!

The crosswalk has length $$$L$$$ and can be modeled as a segment on the $$$x$$$-axis with endpoints at $$$x = 0$$$ and $$$x = L$$$. There are $$$N$$$ pedestrians on the $$$x$$$-axis, not necessarily on the crosswalk. Each pedestrian has an initial position $$$X$$$ and a constant velocity $$$V$$$ (positive or negative); this means that at each time $$$t \ge 0$$$ the position of the pedestrian is $$$X + t \cdot V$$$.

Nathan's car has width $$$C$$$ and he can cross the street if there is a gap of width at least $$$C$$$ between two consecutive pedestrians on the crosswalk or between a pedestrian and an endpoint of the crosswalk. He can also cross if there are no pedestrians on the crosswalk.

You will be given $$$Q$$$ queries. Each query specifies an integer time $$$T \ge 0$$$ and you must decide whether Nathan can cross the street at that moment. Disclaimer: The organization of Programadores de América (PDA) does not condone crossing red lights nor breaking the law. This is a fictional story and the behavior of Nathan does not represent the opinions of the organization of the competition.