After a terrible storm, you receive the locations of $$$n$$$ people waiting to be rescued. To protect them until help arrives, you can create a safety zone in the shape of an equilateral triangle. The safety zone may be placed anywhere and rotated by any angle. A person is protected if their location is inside the triangle or on its boundary.

Since a larger safety zone requires more energy, you want to make it as small as possible. Find the minimum possible area of a safety zone that protects all $$$n$$$ people.

Recall that a triangle is called an equilateral triangle if and only if all its sides have the same length.

Watermelon is a kindergarten teacher who needs to invent games for her energetic kids.

One day, she invented a new game. First, she gathered $$$n$$$ kids and drew a circle on the ground. Every kid is out of the circle initially. The $$$i$$$-th kid is assigned a number $$$a_i$$$. She then announced the rules:

• The kids must determine a permutation and submit it to her, she will call the kids one by one according to the permutation.
• Once a kid is called, he will step into the circle. Then, let $$$a_i$$$ be the number assigned to this kid, all kids currently in the circle must divide themselves into groups of size $$$a_i$$$. Kids not in any group will be removed out of the circle. The kids can determine who to leave the circle, as long as the remaining kids in the circle can be divided into groups of size $$$a_i$$$.
• The game ends when every kid has been called. A kid who has been removed out of the circle cannot be called again. When the game ends, each kid still in the circle receives a cookie as a reward.

Since the kids are cooperative, they will share the cookie after the game ends. Thus, they only care about the total number of the cookie that Watermelon will give out. Please help the kids determine the order in which they should be called so that they obtain the maximum number of cookies.

Note that if a circle contains no kids, it is considered to be divided into groups of size $$$x$$$ for any positive integer $$$x$$$.

You are given a simple undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ black edges. The $$$i$$$-th black edge connects vertices $$$u_i$$$ and $$$v_i$$$. For every pair of distinct vertices not connected by a black edge, there is a white edge between them.

We call two distinct vertices $$$x$$$ and $$$y$$$ close to gray if both of the following conditions hold:

• It is possible to travel from $$$x$$$ to $$$y$$$ using only black edges.
• It is possible to travel from $$$x$$$ to $$$y$$$ using only white edges.

Find the number of unordered pairs $$$(x, y)$$$, where $$$1 \leq x \lt y \leq n$$$, that are close to gray.

You are given an array $$$a$$$ of length $$$n$$$. For each $$$k$$$ from $$$2$$$ to $$$n$$$, find the maximum distance between two distinct elements within any subarray of length $$$k$$$.

Formally, for each $$$k$$$, we want to find:

$$$$$$\max \{ j - i \mid 1 \le i \lt j \le n, \, j - i \lt k, \, a_i \neq a_j \}$$$$$$

If no such pair of distinct elements exists for a given $$$k$$$, the answer is $$$-1$$$.

This story is a work of fiction. Any similarity to real persons or events is coincidental.

After competing in the regional contest of the Fruit Kingdom, the team vegetable_advantages officially concluded their ICPC journey. However, this was also a new beginning because they wanted to give back to society: whenever they saw a problem, they would try to make it harder. While waiting for their flight back from the Fruit Kingdom to the Vegetable Kingdom, they happened to see this problem (which originated from 2025 National High School Programming Contest Problem C):

"A-Ming bought an electric vehicle with a battery capacity of $$$B$$$. A-Ming knows the initial battery level $$$b$$$, and he wants to plan a route from the starting point $$$s$$$ to the destination $$$t$$$ such that the total charging cost is as low as possible.

The electric vehicle consumes battery power on certain road segments (such as flat roads or uphill roads) and charges the battery on other road segments (such as downhill roads). These charging road segments are completely free of charge. We represent the map using a directed graph, where the weight of an edge indicates the increase or decrease in battery level when driving across this edge. If driving through this edge charges the battery, the weight is a positive integer; conversely, if it consumes power, the weight is a negative integer. We assume that the graph has no positive cycles.

While driving, the electric vehicle's battery level must always remain greater than or equal to $$$0$$$, and no matter how much it charges, the battery level can at most reach $$$B$$$. More specifically, let $$$p$$$ be the current battery level of the electric vehicle, and consider an edge with weight $$$w$$$: if $$$w$$$ is non-negative, the electric vehicle can definitely drive through this edge (even if the battery level $$$p=0$$$), and the remaining battery level will be $$$\min(B, p+w)$$$; if $$$w$$$ is negative and $$$p+w \ge 0$$$, the electric vehicle can drive through this edge, and the remaining battery level after passing through will be $$$p+w$$$; however, if $$$p+w \lt 0$$$, the electric vehicle cannot drive through this edge.

Some vertices on the map are charging stations. A-Ming can pass through multiple charging stations. Because charging takes time to find a charging pile, A-Ming decided to use at most one charging station to charge during the entire trip. Charging one unit of battery at a charging station costs one dollar. A-Ming's goal is to reach the destination while spending the least amount of money."

Cabbage, a member of vegetable_advantages, felt that A-Ming was far too lazy for being willing to use only one charging station! Besides, isn't A-Ming curious about the answers from the fixed starting point $$$s$$$ to every possible destination $$$t=1,2,\dots,n$$$? Therefore, on the plane, they solved the version where one can charge at any number of charging stations and must output the answers for $$$t=1,2,\dots,n$$$, and decided to use it to test you.

Flowers may eventually wither, but the shapes they once formed can still be preserved on paper.

A botanist wishes to recreate a garden with as many flowers as possible on an $$$n \times m$$$ grid. Every cell of the grid must belong to exactly one flower. To represent a garden containing $$$k$$$ flowers, each cell is assigned an integer from $$$1$$$ to $$$k$$$, where a cell labeled $$$i$$$ belongs to the $$$i$$$-th flower.

Each of the $$$k$$$ flowers must occupy at least two cells. Moreover, for each flower, all cells belonging to it must be 4-connected. In other words, one must be able to travel between any two cells of the flower by moving only between side-adjacent cells belonging to the same flower.

The flowers in this garden must also be intertwined so that the grid cannot be separated into two parts by a single horizontal or vertical cut along grid lines. More precisely:

• For every pair of consecutive rows, there must be at least one flower that occupies cells both above and below the line between them.
• For every pair of consecutive columns, there must be at least one flower that occupies cells both to the left and to the right of the line between them.

Find the maximum possible number of flowers and construct a corresponding grid.

Did you know that cactus graphs once enjoyed a glorious era in Taiwan's competitive programming scene, especially in 2022?

Looking back, the 2021 NTU ICPC Team Preliminary Contest featured a problem that required answering multiple shortest-path distance queries on a cactus graph$$$^{\text{∗}}$$$, marking the beginning of the Great Cactus Era. In 2022, cactus graphs reached the height of their glory. First, IOICamp featured a problem about answering maximum contiguous path-sum queries between pairs of vertices in a cactus graph$$$^{\text{†}}$$$. Later, YTP featured a problem asking for the maximum-weight independent set of a cactus graph$$$^{\text{‡}}$$$. Incidentally, this problem was so difficult that even the first-place team solved every problem except this one! Finally, that year's NTU ICPC Team Preliminary Contest featured yet another problem combining cactus graphs with linear basis$$$^{\text{§}}$$$.

Unfortunately, since 2023, cactus graphs have almost completely disappeared from programming contests in Taiwan. What a shame! Now, you are given a simple, connected, undirected cactus graph with $$$n$$$ vertices and $$$m$$$ edges. Each edge has a positive integer weight. There is a set of vertices $$$S$$$ which is initially empty. Please process $$$q$$$ operations. Each operation specifies a vertex $$$v$$$ and toggles whether $$$v$$$ belongs to $$$S$$$. That is,

• If $$$v \in S$$$, remove $$$v$$$ from $$$S$$$;
• If $$$v \notin S$$$, add $$$v$$$ to $$$S$$$.

After each operation, output the maximum shortest-path distance between any two vertices in $$$S$$$. That is, let $$$d(u,v)$$$ be the length of the shortest path between vertices $$$u$$$ and $$$v$$$. You should output

$$$$$$ \max_{u,v\in S} d(u,v) $$$$$$

after each operation. Note that if $$$|S| \leq 1$$$, the answer is defined to be $$$0$$$.

To make the problem more interesting, all operations are encoded and must be processed online. See the input format for details.

Note that an undirected graph is called a cactus graph if every edge belongs to at most one simple cycle.

If you ask Doludu and DoIudu what their favorite shape is, they will definitely say it is a hexagon. Because they really love hexagons so much, no matter what object it is, they always want to design it in a hexagonal shape, and game items are no exception.

Today, they are going to play a game. In this game, there are $$$N$$$ hexagonal blocks lined up in a row at the beginning, and these hexagonal blocks are divided into blue and red. After the game starts, the two of them will take turns to make a move, with Doludu going first. When it is a player's turn, he must remove either the leftmost or the rightmost block among the currently remaining blocks. At the moment when only one block is left, the game ends. If this block is blue, Doludu wins; otherwise, DoIudu wins.

Both Doludu and DoIudu are extremely smart and will definitely use the optimal strategy to play this game. Based on the initial colors of the $$$N$$$ blocks, please determine who will win among them.

Given a permutation $$$a$$$ from $$$1$$$ to $$$n$$$, an inversion is defined as a pair of indices $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$ and $$$a_i \gt a_j$$$.

Counting the total number of inversions is an extremely classic problem. In this problem, we consider a variation.

For each $$$k$$$ from $$$1$$$ to $$$n-1$$$, find the number of pairs $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$, $$$j - i = k$$$, and $$$a_i \gt a_j$$$.

In the Grand Palace of the Fruits Kingdom, there is a long ornamental chain consisting of $$$n$$$ decorative beads, numbered from $$$1$$$ to $$$n$$$ from left to right. Initially, all beads are uncolored.

To celebrate the upcoming Fruits' Festival, the King has invited $$$m$$$ jesters to color the beads. The jesters are numbered from $$$1$$$ to $$$m$$$. The coloring process runs for $$$m$$$ turns, in the $$$i$$$-th turn, the $$$i$$$-th jester must paint a contiguous segment of the beads with color $$$i$$$. However, the jesters do not view themselves as ordinary performers, instead, all of them are strictly adhered to the sacred number $$$k$$$, insisting that each jester's stroke must cover exactly $$$k$$$ beads. It follows that each jester has $$$n - k + 1$$$ choices in their turn.

Note that painting a colored bead will overwrite its original color.

Since the jesters are paid, the king does not want to see uncolored beads at the ceremony. Thus, all $$$n$$$ beads must be painted by at least one of the jesters by the end of the process.

Please help the King calculate the total number of possible final states of the beads that satisfy the condition above. Two final states are considered different if and only if there exists a bead $$$i$$$ that has a different color in the two states. Since the answer could be large, output it modulo $$$p$$$.

Six seven. Six seven. 67, 67, 67.

"It's joever; pack it up," you thought. The brainrot trend has gone too far. It is the end of society.

First they came as skibidi toilet, and you did not speak out. Because you thought that was fine. Then they came as tralalero tralala, and you did not speak out. Because you thought that was nonsense. Then they released the game Tung Tung Sahur Extreme, and you did not speak out. Because you thought no one cared about that. Then they came as six seven, and there was no one left to speak for you. The problem title itself, you realized, it means "six seven" in Finnish. You are finished.

All that is left, is a string. You are given a string $$$S$$$. It can contain three different characters: six (6), seven (7), and — if you think that's enough, it is not — ASCII code 67: upper case Latin alphabet C.

This is your final chance. Even if it might be futile, you would still want to try for the very last time. You must replace each ASCII code 67 character with one of six (6) or seven (7). Your goal is to minimize the number of subsequences of the string that are identical to six seven (67).

Two subsequences are considered different if there exists at least one position that is in one but not the other.

This is Mango's dark history.

One day, he learned about the linear sieve, an algorithm capable of computing multiplicative functions, such as $$$\phi(n)$$$ and $$$\mu(n)$$$, in linear time. However, when explaining this algorithm to his teammates, he made a silly mistake. He confused the abbreviation LPF with Largest Prime Factor, as it is quite natural for a non-native English speaker to mistake least for largest.

To ensure he never forgets this embarrassing moment, he brings this problem to you. Given an integer $$$r$$$, calculate $$$$$$ \sum_{i=1}^r G(i) $$$$$$ where $$$G(i)$$$ denotes the largest prime factor of $$$i$$$. He uses the letter $$$G$$$ because it is more common to call it Greatest Prime Factor.

For convenience, define $$$G(1) = 0$$$.

In a certain RPG, there are $$$n$$$ slimes lined up in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. Each slime can be of water-type, fire-type, or elementless. The power of the $$$i$$$-th slime is represented by a signed integer $$$a_i$$$. Specifically:

• If $$$a_i \gt 0$$$, the slime is of water-type, and its power is $$$a_i$$$.
• If $$$a_i \lt 0$$$, the slime is of fire-type, and its power is $$$\vert{}a_i\vert{}$$$ (which is equal to $$$-a_i$$$).
• If $$$a_i = 0$$$, the slime is elementless, and its power is $$$0$$$ (representing no energy or power value).

As a player, you will use a water-type magic to attack these slimes. The mana cost to attack a single slime is determined as follows:

• If its represented power $$$a_i \gt 0$$$, the mana cost is $$$a_i$$$.
• If its represented power $$$a_i \le 0$$$ (meaning the slime is fire-type or elementless), the mana cost is $$$0$$$.

To minimize the total mana cost, you can perform at most $$$k$$$ merging operations before casting the magic:

• Select two adjacent slimes with represented powers $$$a$$$ and $$$b$$$, and merge them into a single slime. The represented power of the newly merged slime will be $$$a+b$$$.

After performing at most $$$k$$$ operations, you cast the magic. The total final cost will be the sum of the mana costs required to attack all remaining slimes.

Find the minimum possible total cost if you use an optimal strategy.