In the high halls of Numeria, an archmage tends to $$$n$$$ magic crystals with powers $$$a_1, a_2, \ldots, a_n$$$. With a fusion spell, he may pick any two crystals with powers $$$x$$$ and $$$y$$$, remove them, and create a single crystal of power $$$x + y$$$. Each spell reduces the number of crystals by 1.

The archmage seeks harmony: he wants the average power of the crystals to become an integer. What is the minimum number of spells he must cast?

In the mystical Academy of Bytelandia, an archmage is studying a line of $$$n$$$ enchanted stones, each with a power value $$$a_1, a_2, \ldots, a_n$$$.

A query spell is defined as follows: for two indices $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq n$$$), the spell reveals the total power of the stones from position $$$L$$$ to $$$R$$$:

$$$$$$ S(L,R) = \sum_{i=L}^{R} a_i $$$$$$

The oracle wonders: what is the total sum of the answers of all possible queries?

Formally, compute:

$$$$$$\left( \sum\limits_{L=1}^N \sum\limits_{R=L}^N S(L, R) \right)$$$$$$

The Legendary Huron owns a long, narrow box filled with magnetic sticks. Each stick has a color. Colors are represented by integers from $$$1$$$ to $$$10^6$$$.

The box can only store sticks in a single line, from left to right. Initially, the box contains $$$n$$$ sticks. You are given an array $$$A$$$ of length $$$n$$$, where $$$A_i$$$ is the color of the $$$i$$$-th stick from left to right.

Over time, the Legendary Huron will perform $$$Q_1 + Q_2$$$ operations on his box. There are four possible operations:

1. Buy a bag of $$$k$$$ sticks of color $$$c$$$ and insert them to the left end of the box.
2. Buy a bag of $$$k$$$ sticks of color $$$c$$$ and insert them to the right end of the box.
3. Remove the leftmost $$$k$$$ sticks from the box and give them to his cousin, Huroncito.
4. Remove the rightmost $$$k$$$ sticks from the box and give them to Huroncito.

After each operation, the Legendary Huron will take the sticks from his box to play with them and attempt to build a colorful polygon using the sticks he currently possesses. A polygon is colorful if it satisfies the following conditions:

• It must be simple with no self-intersections and have a positive area.
• Each side of the polygon must consist of sticks of the same color.
• No two sides may share the same color.
• The length of a side equals the number of sticks used for that side.

For example, if the box has the following sticks $$$[4,3,1,1,2,3,3,4,4]$$$, where different integers represent different colors, a valid colorful polygon could be a triangle. One side may consist of two sticks of color $$$1$$$, another side of three sticks of color $$$3$$$, and the last side of two sticks of color $$$4$$$. The total perimeter in this case is $$$7$$$. Note that it is not necessary to use all colors or all sticks of a color.

Each time he plays with the sticks, the Legendary Huron asks for the maximum perimeter of a colorful polygon that can be constructed. If no colorful polygon can be formed, the result is $$$0$$$. After playing with the sticks, they are stored in the same order as before in the box.

The first $$$Q_1$$$ operations are given explicitly in the input. The last $$$Q_2$$$ operations, however, are not given directly. Instead, they are generated using a random generator described in the Input section. Read the Output section to see how to print the answer for the last $$$Q_2$$$ operations.

Let's be direct. No stories, no worries. You will be given an integer $$$n$$$ and you must determine if there is a sequence $$$a$$$ of length $$$2n$$$ such that:

• Each value from $$$1$$$ to $$$n$$$ occurs exactly twice in $$$a$$$.
• For each $$$i = 1, \ldots, n$$$, the distance between both of its occurrences is exactly $$$i + 1$$$. This is, let $$$L_{i}$$$ and $$$R_{i}$$$ be the leftmost and rightmost occurrence of $$$i$$$, respectively. Then, $$$R_{i} - L_{i} = i + 1$$$.

If there is at least one sequence, print it. Otherwise, print -1.

It's time for the first game of the global edition of the Squid Games.

The game is played in a tower with $$$n$$$ floors numbered from $$$1$$$ to $$$n$$$, each floor containing $$$k$$$ rooms numbered from $$$1$$$ to $$$k$$$. There are $$$m$$$ stairs; the $$$i$$$-th stair connects room $$$u_i$$$ on floor $$$f_i$$$ with room $$$v_i$$$ on floor $$$f_i + 1$$$.

There are $$$2\cdot10^9$$$ players invited to play the game. At the beginning, each of the $$$2 \cdot 10^9$$$ players must choose any room on the first floor. The game lasts for $$$n$$$ turns. In turn $$$t$$$ ($$$1 \le t \le n$$$), the following actions occur in order:

1. For every room $$$j$$$ on floor $$$t$$$, if there are more than $$$C_{t,j}$$$ players, random players are eliminated until exactly $$$C_{t,j}$$$ remain in that room.
2. If $$$t \lt n$$$, each surviving player in a room on floor $$$t$$$ must move to a room on floor $$$t+1$$$ using one of the available stairs connected to their current room. Players unable to move are eliminated. Moving down is not allowed.
3. If $$$t = n$$$, all surviving players are declared winners of the first game, and the game ends.

Player 456 wants to maximize the number of players who survive. For each turn $$$t$$$, compute the maximum number of players that can be alive at the end of that turn, assuming optimal choices for the initial distribution and movements. Note that for each $$$t$$$, these values are calculated independently.

The Fantastic Four have been defeated by the evil Doctor Doom, and are being held hostage in his castle in Latveria, and it's up to HERBIE the robot to save them. HERBIE has managed to infiltrate the castle and now just needs to reach the cell where the Fantastic Four are held to free them.

Doom's castle can be represented as 2D binary matrix of $$$NxM$$$. If a cell has a value of $$$1$$$ it means there is a wall there, while a $$$0$$$ means it's a free space. HERBIE can move only through free spaces, but since he's a robot he can only move in some specific ways.

HERBIE can follow one of 4 possible $$$\bf{instructions}$$$. Assuming HERBIE is on position $$$(x,y)$$$ then:

- $$$U$$$ means HERBIE will try to move to $$$(x-1,y)$$$

- $$$D$$$ means HERBIE will try to move to $$$(x+1,y)$$$

- $$$L$$$ means HERBIE will try to move to $$$(x,y-1)$$$

- $$$R$$$ means HERBIE will try to move to $$$(x,y+1)$$$

If the position HERBIE is trying to move to is a wall or it's outside of the matrix, HERBIE will simply not move and continue with the next instruction.

However HERBIE can't just do any instruction he wants, he has to follow one of its many preprogrammed $$$\bf{orders}$$$. An $$$\bf{order}$$$ is an ordered set of instructions. If HERBIE chooses to execute certain order, then he has to do all of the movements described in it and in their given order, without changing them around.

As time is running out, HERBIE wants to reach the Fantastic Four moving the least amount of time. He has asked you to help him find out the minimum amount of movements he has to do to reach the Fantastic Four and save them! To properly save them HERBIE has to finish at their cell after he completes the instructions of an order. Passing by the cell while not completing an order doesn't count as reaching them.

The once-kind feline Gatuno is a very good and heart-guided person. As every good person, his goodness can be measured. He carries a heart of size $$$H_1$$$. Unfortunately, now he seeks to shed his humanity. His twisted goal: reduce his heart to size $$$H_2$$$ or smaller through a horrifying ritual — biting innocent dogs.

Each bite comes at a terrible cost to his remaining conscience, but makes subsequent bites easier in his dark transformation...

After biting $$$n$$$ dogs, the rule of shrinking heart is:

- His heart shrinks: $$$ H_{n} = H_1 \times \left(\frac{B-1}{B}\right)^n $$$ Therefore, each subsequent bite requires $$$ \frac{1}{B} $$$ of the previous emotional pain.

Help Gatuno to find the minimum minimum number of dogs Gatuno must bite to reduce his heart size to $$$H_2$$$ or smaller.

In the Library of Acatlán, an ancient spell is written as a long string $$$S$$$ of length $$$N$$$. The spell also contains a secret incantation $$$T$$$, a string of length $$$M$$$.

The power of the spell is measured by the number of subsequences of $$$S$$$ that are equal to $$$T$$$.

The oracle of Acatlán allows you to perform at most one modification on $$$S$$$: you may change a single character in $$$S$$$ to any other lowercase English letter.

Your task is to count the power of all the possible spells with at most one modification.

Definition: A string $$$U$$$ is called a subsequence of a string $$$V$$$ if $$$U$$$ can be obtained from $$$V$$$ by deleting zero or more characters without changing the relative order of the remaining characters.

Isaac is a passionate competitive programmer, especially fascinated by convolution techniques used in ICPC problems. During the lectures of last year's Training Camp Mexico (TCMX for short), he mastered bitwise convolutions:

• AND convolution: for each $$$k$$$, $$$$$$ C[k] = \sum_{i \,\&\, j = k} A[i] \cdot B[j] $$$$$$
• OR convolution: for each $$$k$$$, $$$$$$ C[k] = \sum_{i \,|\, j = k} A[i] \cdot B[j] $$$$$$
• XOR convolution: for each $$$k$$$, $$$$$$ C[k] = \sum_{i \,\oplus\, j = k} A[i] \cdot B[j] $$$$$$

He implemented all of them successfully with SOS DP and used them to solve problems involving fast subset transforms.

This year, during the Tercera Fecha del Gran Premio de México ICPC 2025, which coincides with the third contest of this year's TCMX, Isaac is facing a problem involving a new and intriguing type: MOD convolution. It is defined similarly to the bitwise convolutions, but replacing the bitwise index condition with a modular remainder condition:

$$$$$$ C[k] = \sum_{\substack{1 \leq i \leq n \\ k \lt j\leq m \\ i \equiv k\bmod{j}}} A[i] \cdot B[j] $$$$$$

As everyone knows, MOD convolution can be easily calculated using $$$\blacksquare\blacksquare\blacksquare$$$.

The problem asks, given arrays $$$A$$$ of length $$$n$$$ and $$$B$$$ of length $$$m$$$, to compute: $$$$$$ \sum_{k=0}^{\infty} k \cdot C[k]. $$$$$$

Where $$$C[k]$$$ is defined as in the MOD convolution above.

Just like Isaac, you are also competing in the Tercera Fecha del Gran Premio de México ICPC 2025, and you should find the answer for this problem.

In ancient times, when the gods still contested the fate of mankind, two immortal brothers clashed in a sacred ritual: Juan, Lord of Chaos, and Frank, Guardian of Order. Before them stood $$$n$$$ ancestral columns, each filled with fragments of divine power.

The brothers played these duels to see who would rule over the mortal realm.

Each duel was foretold by a prophecy, specifying the columns from $$$l$$$ to $$$r$$$. Within this range, the brothers engaged in their duel under unbreakable laws:

• Frank always starts the duel.
• The players alternate turns.
• On their turn, a player had to choose one column and remove any positive number of fragments from it.
• The one who faced an empty field, with no fragments left to remove, was defeated.
• Both players play optimally.

The high priests, gifted with the power of foresight, have recorded $$$Q$$$ events. Each event is either:

- A prophecy, foretelling a duel over a range of columns $$$(l,r)$$$.

- A ritual, adding $$$x$$$ fragments to column $$$k$$$, altering its power.

Now, the temple calls upon you to ensure the chronicles of Order and Chaos remain true

On the Pan-American Highway, two maintenance crews work on different road segments. Each segment is a closed interval on a line (in kilometers). To coordinate resources, we only need the length of the overlap between both segments.

Given two closed intervals $$$[a,b]$$$ and $$$[c,d]$$$ (with $$$a \le b$$$ and $$$c \le d$$$), print the length of their intersection on the real line. If they do not overlap (or only touch at a single point), the length must be $$$0$$$.

The length of a closed interval $$$[x,y]$$$ is defined as $$$y - x$$$.

In the distant hills, there was the city of Ratonia, home of the Ratones. Its streets were connected in a very special way: between any two houses, there was exactly one unique path.

Each house in Ratonia had a unique identifier (from 1 to N). Additionally, every street connecting two houses had its own value (from 1 to 1000000000).

After returning from a tournament, the Ratones received Q letters from their fans.

In every letter, the fans asked the same request:

"Dear Ratones, could you tell us the sum of all edge values along the path that connects the house with identifier u and the house with identifier v after multiplying the hole path by x?"

Since the Ratones don't know how to answer these requests themselves, they have asked for your help.