Xiao Ming bought a ribbon with $$$n$$$ segments. The $$$i$$$-th segment initially has color $$$c_i$$$. Xiao Ming prefers solid-colored ribbons, so he needs to paint every segment of this ribbon the same color.

For a painting operation $$$(l, r, c)$$$, it means that the interval $$$[l, r]$$$ of the ribbon can be painted with color $$$c$$$ at a cost of $$$w_c + (r - l + 1)$$$, where $$$w_c$$$ is the price of color $$$c$$$.

Now, for each color $$$c = 1, 2, ..., n$$$, please determine the minimum cost for Xiao Ming to paint the entire ribbon into color $$$c$$$.

Xiao Ming installed $$$n$$$ lights in his new home but forgot to install switches. So he hired $$$m$$$ electricians to install switches for him. These $$$m$$$ electricians are all novices who came to practice switch installation at Xiao Ming's home, so they don't charge for their work.

The electricians arrive and work one by one. When the $$$i$$$-th electrician arrives, he brings a switch and selects $$$k$$$ lights $$$a_1,a_2,...,a_k$$$ from the $$$n$$$ lights to connect them together. Each time this switch is pressed, every one of these $$$k$$$ lights will toggle its state (on becomes off, off becomes on).

Since these novice electricians are here to practice, the set of lights they connect must satisfy the following condition: $$$\mathbf{At\ least\ one\ of\ the \ lights\ connected \ by\ their\ switch\ was \ previously\ connected\ by}$$$$$$\mathbf{\ at\ most\ one\ switch\ before\ theirs.}$$$

After living there for several years, Xiao Ming suddenly discovered that all the switches in his home had broken, but some lights were still on. Due to the passage of time, Xiao Ming could no longer remember the original installation order of the switches, $$$\mathbf{and\ all\ switches\ have\ been\ renumbered}$$$. Now these novice electricians have all become senior electricians, and repairing the $$$i$$$-th switch costs $$$c_i$$$ yuan.

Xiao Ming wants to know the minimum amount of money needed to repair the switches so that he can now turn off all the lights.

Given positive integers $$$a,b$$$. Find a positive integer $$$x$$$ such that:

• $$$1 \leq x \leq 10^{18}$$$.
• $$$\gcd(a,x)=1$$$ and $$$\gcd(b,x) \gt 1$$$.

If it is impossible to find such an integer $$$x$$$, output $$$-1$$$.

Here $$$\gcd(a,b)$$$ denotes the greatest common divisor of $$$a$$$ and $$$b$$$, which is the maximum positive integer that divides both $$$a$$$ and $$$b$$$.

Xiao Ming dreamed that he bought a stock with an initial price of $$$v$$$ yuan, which then rose for $$$n$$$ consecutive trading days. Xiao Ming was so happy in his dream.

After waking up, Xiao Ming realized he could only remember whether the stock price increased by $$$x_i$$$ times or increased by $$$x_i$$$ yuan compared to the previous day for each of these $$$n$$$ trading days.

But Xiao Ming soon discovered a problem: rearranging these $$$n$$$ pieces of information could clearly make the average closing price of the stock over these $$$n$$$ trading days larger. Please help Xiao Ming rearrange the order of these $$$n$$$ pieces of information to maximize the average closing price after these $$$n$$$ trading days.

Formal problem statement:

There is a variable $$$v$$$ and $$$n$$$ operations, where the $$$i$$$-th operation is either $$$\times x_i$$$ or $$$+x_i$$$, and the operator is denoted as $$$\text{op}_i$$$.

You need to determine a permutation $$$p_1,...,p_n$$$ and compute $$$v_0=v,v_i=v_{i-1}\ \text{op}_{p_i}\ x_{p_i}$$$.

Maximize $$$\frac{v_1+v_2+...+v_n}{n}$$$.

Xiao Ming is learning to type using a keyboard. Today, he needs to input a string $$$s$$$ of length $$$n$$$ consisting of lowercase letters only.

Initially:

Xiao Ming's left index finger is on the lowercase letter 'a' on the keyboard.

His right hand is used to press the left/right arrow keys to control the cursor position.

Xiao Ming starts with an empty string $$$s$$$, and the cursor is at the very beginning of the string. Each second, he can perform one of the following three operations:

1. Move his left index finger from the current letter $$$x$$$ to letter $$$y$$$, with a cost of $$$\text{cost}_{x,y}$$$.

2. Press the left or right arrow key to move the cursor left/right by one position, with a cost of $$$t$$$. If the cursor is already at the far left/right, nothing happens.

3. Press the letter currently under his left index finger to print the character to the right of the cursor in the string, with a cost of $$$t$$$.

For example, to print the string $$$\text{aabaa}$$$, Xiao Ming can proceed as follows: 1. Press 'a' four times with his left hand (cost: $$$4t$$$). Now $$$\text{s=aaaa}$$$, cursor after the fourth 'a'. 2. Press the left arrow key twice with his right hand (cost: $$$2t$$$). Now $$$\text{s=aaaa}$$$, cursor after the second 'a'. 3. Move his left hand from 'a' to 'b' (cost: $$$\text{cost}_{a,b}$$$), then press 'b' (cost: $$$t$$$). Now $$$\text{s=aabaa}$$$, cursor after 'b'.

Please help Xiao Ming calculate the minimum total cost required to print the target string $$$s$$$.

"Another cycle past U, then. What a shocker."

After guiding Saturday's group to the underground where the truth was kept, Dawn was brought to somewhere unknown by the Worldkeeper, also known as Tsuki. There is no doubt that the duel of LOCK S is about to begin.

The battlefield takes the shape of a rooted tree with $$$n$$$ nodes, numbered $$$1$$$ to $$$n$$$, with $$$1$$$ being the root of the tree. Each node has a terrain vantage point, with the $$$i$$$-th node having a terrain vantage point of $$$v_i$$$. Dawn and Tsuki will fight here, taking turns occupying each node in the tree until they finally meet up and start fighting. Since Dawn is far more skilled at synchronizing with Layer 1 than Tsuki is after practicing with the LOCK P, V, and U, she will be the first to act in this node battle, followed by Tsuki, then Dawn's turn......, and so on.

Both Dawn and Tsuki start off outside the field. At the start of one's turn, she will choose a node that is not occupied by anyone that meets her action condition, move to that node, and occupy the node she moves to. When it is one person's turn to move but she does not have a node that meets the aforementioned conditions, she will choose to immediately meet the other one to begin the duel. The action conditions for both players are shown below:

• Dawn: Due to Dawn's proficiency in synchronizing with Layer 1, she can choose any node $$$v$$$ and move to it, independent of which node she is currently at.
• Tsuki: When Tsuki is outside the field, she can only move to node $$$1$$$. After that, she can only choose one of the sons of the node she is in, and that son has the largest terrain vantage point of all the unoccupied sons. Specifically, if there is more than one son that satisfies the condition, she chooses the one with the smallest number.

Dawn believes that as long as the sum of the terrain vantage point of the nodes she occupies, minus the sum of the terrain vantage point of the nodes Tsuki occupies, is maxed out at the time of the duel, she will survive LOCK S and perform a miracle. However, she doesn't know how to calculate this value, so she has to put all her hopes on you who are in Layer 4. Please help her calculate this maximum difference.

There are $$$n$$$ students standing in a line, and the $$$i$$$-th student from the left has an exam score of $$$a_i$$$.

A teacher wants to assess the learning situation of these students. Specifically, each time he can choose to check the score of the $$$i$$$-th student. If at least one of the following conditions is met, the student will leave the line:

• In the current line, there exists a student to the left of the $$$i$$$-th student with a score not less than $$$a_i$$$, and there exists a student to the right with a score not greater than $$$a_i$$$.
• In the current line, there exists a student to the left of the $$$i$$$-th student with a score not greater than $$$a_i$$$, and there exists a student to the right with a score not less than $$$a_i$$$.

The teacher wants as many students as possible to leave the line. Your task is to determine the minimum number of students remaining in the line in the end.

Xiaoming is a little kid who loves eating candy and sleeping.

Because eating too much candy can cause cavities, Xiaoming has made an $$$n$$$-day candy-eating plan for himself.

Xiaoming gets sad when he can't eat candy, so he uses a mood level to represent his mood each day. On day $$$0$$$, his mood is $$$0$$$.

Xiaoming's candy-eating plan is described by a string $$$s$$$ of length $$$n$$$ containing only $$$\texttt{01}$$$. For the $$$i$$$-th day of the plan:

• If $$$s_i=\texttt{1}$$$, it means Xiaoming will eat a piece of candy on the $$$i$$$-th day, and his mood will increase by $$$1$$$;
• If $$$s_i=\texttt{0}$$$, it means Xiaoming will not eat candy on the $$$i$$$-th day to prevent cavities, and his mood will decrease by $$$1$$$.

Xiaoming believes that the higher his mood, the more perfect the plan is. Therefore, the perfection of the plan is defined as the maximum mood level he reaches during days $$$0$$$ to $$$n$$$.

However, since Xiaoming is a sleepy little kid, each day he has a $$$\dfrac{1}{2}$$$ probability of sleeping and skipping his plan for the day, and a $$$\dfrac{1}{2}$$$ probability of following the plan as usual.

If Xiaoming chooses to sleep on a certain day, he will not eat candy, and his mood will remain unchanged.

Xiaoming's decisions each day are independent (sleeping or following the plan). Please help him calculate the expected perfection of the plan.

Since the answer may not be an integer, you only need to output the answer modulo $$$998244353$$$.

Specifically, the answer can always be expressed as a rational number $$$\dfrac{p}{q}$$$, where $$$p,q$$$ are coprime, and $$$q$$$ is not a multiple of $$$998244353$$$.

You need to find the unique integer $$$x$$$ satisfying $$$x\times q\equiv 1\pmod {998244353}$$$, and then output the value of $$$xp\bmod 998244353$$$.

Given an integer sequence of length $$$n$$$, $$$b_1, b_2, \dots b_n$$$, and a magic parameter integer $$$k$$$. To perform one magic operation, you need to select a positive integer $$$x$$$ such that $$$k \le x \le n - k$$$, set the integer $$$t = b_{x + 1} - b_x$$$, and then perform the following operations:

• For all positive integers $$$d$$$ satisfying $$$1 \le d \le k$$$, subtract $$$t$$$ from $$$b_{x + d}$$$ and add $$$t$$$ to $$$b_{x - d + 1}$$$.

Now you need to determine how many different sequences $$$b_1, b_2, \dots b_n$$$ can be obtained after performing any number of magic operations (including $$$0$$$ operations). Since the answer may be large, you only need to output the result modulo $$$10^9 + 7$$$.

It can be proven that there are only a finite number of possible sequences $$$b$$$. Two sequences $$$S$$$ and $$$T$$$ are considered different if there exists some position $$$z$$$ such that $$$S_z \ne T_z$$$.

Xiao Tang and Xiao Ming had an argument, and Xiao Tang lost. But Xiao Tang really wants to win, so he's trying to find evidence that he actually won.

Xiao Ming posted a travel story on his social media, and Xiao Tang wants to extract evidence of Xiao Ming admitting defeat from it.

Specifically: Xiao Tang has converted Xiao Ming's story into a lowercase string $$$s$$$ of length $$$n$$$, where the $$$i$$$-th character is $$$s_i$$$.

Xiao Tang can perform the following operation at most $$$k$$$ times:

Insert any character at any position in $$$s$$$.

Please help Xiao Tang calculate, assuming he performs the operations optimally, what is the maximum number of substrings "lose" he can find in $$$s$$$.

Note: This problem requires finding substrings (contiguous sequences), not subsequences.

Farmer Steve wants to provide welfare for the cows on his farm!

Steve has a lot of grass to distribute to the cows, but he wants to give them the right to choose. So he sets up two options A and B. Cows that choose A will share $$$x$$$ kilograms of grass (that is, if there are $$$k$$$ cows that choose A, and $$$k \gt 0$$$, then each of these $$$k$$$ cows will receive $$$\frac{x}{k}$$$ kilograms of grass, without rounding), while cows that choose B will individually receive $$$y$$$ kilograms of grass.

On Steve's farm, there are $$$n$$$ selfless cows and $$$m$$$ selfish cows. Steve has a good relationship with the cows; he knows which cows are selfless and which are selfish, and each cow knows the values of $$$x$$$ and $$$y$$$. The selection process follows these steps:

1. If $$$n \gt 0$$$, all selfless cows elect the smartest among them to decide how each selfless cow should choose, so that the total weight of grass received by all cows is maximized. The selfless cow knows how the selfish cows will decide what to choose.
2. If $$$m \gt 0$$$, all selfish cows make their choices independently and simultaneously. They know the choices of the selfless cows. A selfish cow will assume that all other selfish cows choose B. In this case, if choosing A gives it a weight of grass that is strictly greater than the weight it would receive by choosing B, it will choose A; otherwise, it will choose B.

Steve has already determined the values of $$$x$$$ and $$$y$$$, and he wants to know how many kilograms of grass he will need to distribute in total to the cows. It can be proven that the answer will always be an integer.

Given a positive integer $$$n$$$, consider an $$$n \times n$$$ matrix $$$a$$$ where the element in the $$$i$$$-th row and $$$j$$$-th column is given by $$$a_{i, j} = (i - 1) \times n + j$$$. Below is an example for $$$n = 4$$$:

$$$$$$ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix} $$$$$$

Your task is to select some numbers from the matrix such that:

• Exactly two numbers are chosen from each row.
• Exactly two numbers are chosen from each column.

You need to determine the minimum sum of the numbers that are selected.

"The story remains unfinished...""Wait a minute, haven't we already escaped from the Duskbreaker??"

It had been a long time since they escaped from that simulated world. One day, Tsuki awakened her consciousness within Saturday's inner world, only to see a familiar yet strange scene before her—a glitchy transition, followed by several locks appearing in front of her. Just like when she broke through LOCK C long ago, these locks described a puzzle, and she needed to find the answer to unlock them. And if she succeeded... perhaps she could escape this nightmare.

The puzzle was as follows:

There is a chain with $$$n$$$ nodes, labeled from $$$1$$$ to $$$n$$$. There are $$$n-1$$$ edges connecting these $$$n$$$ nodes, where the $$$i$$$-th edge connects node $$$i$$$ and node $$$i+1$$$. Each point has a weight $$$w_i$$$ and a color $$$c_i$$$, where $$$c_i$$$ can only be either black or white.

Starting from the $$$1$$$st moment, the chain undergoes color changes at each time step. Specifically, we examine every maximal monochromatic connected component on the chain. If a connected component has an adjacent heavier connected component of the opposite color, then all nodes in this connected component will flip their color (black becomes white, and white becomes black). Note that all connected components flip their colors simultaneously.

A connected component $$$S$$$ is considered heavier than another connected component $$$T$$$ if and only if the total weight of all nodes in $$$S$$$ is greater than that of $$$T$$$, or if their weights are equal and the smallest-numbered node in $$$S$$$ has a smaller index than the smallest-numbered node in $$$T$$$.

Beside the puzzle, there were $$$q$$$ markers indicating how to extract information from this process as the solution. The $$$i$$$-th marker was a pair of positive integers $$$(t_i,x_i)$$$, representing the color (black or white) of the $$$x_i$$$-th node at the $$$t_i$$$-th moment as the answer.

Tsuki, being not very skilled at solving puzzles, asked for your help to determine the answers corresponding to these $$$q$$$ markers so she could crack the puzzle and escape this nightmare.