apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ disks in the plane. The center of each disk has integer coordinates, and the radius of each disk is a positive integer. No two disks overlap in a region of positive area, but it is possible for disks to be tangent to each other.

Your task is to determine whether it is possible to change the radii of the disks in such a way that:

- Disks that were tangent to each other remain tangent to each other.
- No two disks overlap in a region of positive area.
- The sum of all radii strictly decreases.

## Input Format
The first line contains an integer $$$n$$$ ($$$1\le n \le 1000$$$) — the number of disks.

The next $$$n$$$ lines contain three integers each. The $$$i$$$-th of such lines contains $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$), and $$$r_i$$$ ($$$1 \leq r_i \leq 10^9$$$) — the coordinates of the center, and the radius, of the $$$i$$$-th disk.

## Output Format
Print $$$\texttt{YES}$$$ if it is possible to change the radii in the desired manner. Otherwise, print $$$\texttt{NO}$$$.

## Examples
```input
5
0 2 1
0 0 1
4 -3 4
11 0 3
11 5 2
```
```output
YES
```
-----
```input
4
2 2 2
7 2 3
7 7 2
2 7 3
```
```output
NO
```

## Note
In the first sample, one can decrease the radii of the first and third disk by $$$0.5$$$, and increase the radius of the second disk by $$$0.5$$$. This way, the sum of all radii decreases by $$$0.5$$$. The situation before and after changing the radii is depicted below.

First sample (left) and a valid way to change the radii of the disks (right).

In the second sample, depicted below, there is no way to change the radii of the disks in the desired manner.

Second sample.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ lamps numbered $$$1$$$ to $$$n$$$ lined up in a row, initially turned off. You can perform the following operation any number of times (possibly zero):

- Choose two non-adjacent$$${}^\dagger$$$ lamps that are currently turned off, then turn them on.

Determine whether you can reach configuration $$$s$$$, where $$$s_i = 1$$$ means the $$$i$$$-th lamp is turned on, and $$$s_i = 0$$$ otherwise.

$$${}^\dagger$$$ Only lamp $$$i$$$ and $$$i + 1$$$ are adjacent for all $$$1 \le i < n$$$. Note that lamp $$$n$$$ and $$$1$$$ are not adjacent when $$$n \ne 2$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 50$$$) — the number of lamps.

The second line of each test case contains a binary string $$$s$$$ of size $$$n$$$ — the final desired configuration.

## Output Format
For each test case, print on one line "YES" if we can reach the configuration $$$s$$$ via applying the given operation any number of times. Otherwise, print "NO".

## Examples
```input
5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111
```
```output
YES
NO
YES
NO
YES
```

## Note
In the first test case, the sequence of operation could have been as follows (note that initially $$$s$$$ is all zero): $$$\mathtt{0000000000} \to \mathtt{\color{red}{1}0000000\color{red}{1}0} \to \mathtt{1\color{red}{1}00000\color{red}{1}10} \to \mathtt{110\color{red}{1}0\color{red}{1}0110}$$$.

In the third test case, we don't have to do any operation.

In the fourth test case, we cannot do any operation, but we need the first lamp to be on. Therefore, it is impossible to achieve the desired state.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$p$$$ of size $$$n$$$, as well as a non-negative integer $$$k$$$. You need to construct a permutation $$$q$$$ of size $$$n$$$ such that $$$\operatorname{inv}(q) + \operatorname{inv}(q \cdot p) = k {}^\dagger {}^\ddagger$$$, or determine if it is impossible to do so.

$$${}^\dagger$$$ For two permutations $$$p$$$ and $$$q$$$ of the same size $$$n$$$, the permutation $$$w = q \cdot p$$$ is such that $$$w_i = q_{p_i}$$$ for all $$$1 \le i \le n$$$.

$$${}^\ddagger$$$ For a permutation $$$p$$$ of size $$$n$$$, the function $$$\operatorname{inv}(p)$$$ returns the number of inversions of $$$p$$$, i.e. the number of pairs of indices $$$1 \le i < j \le n$$$ such that $$$p_i > p_j$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5, 0 \le k \le n(n - 1)$$$) — the size of $$$p$$$ and the target number of inversions.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$'s are pairwise distinct) — the given permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print on one line "YES" if there exists a permutation $$$q$$$ that satisfies the given condition, or "NO" if there is no such permutation.

If the answer is "YES", on the second line, print $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ that represent such a satisfactory permutation $$$q$$$. If there are multiple such $$$q$$$'s, print any of them.

## Examples
```input
5
3 4
2 3 1
5 5
2 3 5 1 4
6 11
5 1 2 3 4 6
9 51
3 1 4 2 5 6 7 8 9
1 0
1
```
```output
YES
3 2 1
NO
NO
YES
1 5 9 8 7 6 4 3 2
YES
1
```

## Note
In the first test case, we have $$$q \cdot p = [2, 1, 3]$$$, $$$\operatorname{inv}(q) = 3$$$, and $$$\operatorname{inv}(q \cdot p) = 1$$$.

In the fourth test case, we have $$$q \cdot p = [9, 1, 8, 5, 7, 6, 4, 3, 2]$$$, $$$\operatorname{inv}(q) = 24$$$, and $$$\operatorname{inv}(q \cdot p) = 27$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Alice and Bob have bought a ribbon consisting of $$$n$$$ parts. Now they want to paint it.

First, Alice will paint every part of the ribbon into one of $$$m$$$ colors. For each part, she can choose its color arbitrarily.

Then, Bob will choose at most $$$k$$$ parts of the ribbon and repaint them into the same color (he chooses the affected parts and the color arbitrarily).

Bob would like all parts to have the same color. However, Alice thinks that this is too dull, so she wants to paint the ribbon in such a way that Bob cannot make all parts have the same color.

Is it possible to paint the ribbon in such a way?

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of one line containing three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le m, k \le n \le 50$$$) — the number of parts, the number of colors and the number of parts Bob can repaint, respectively.

## Output Format
For each test case, print YES if Alice can paint the ribbon so that Bob cannot make all parts have the same color. Otherwise, print NO.

You can print every letter in any register. For example, Yes, yes, yEs will all be recognized as positive answer.

## Examples
```input
5
1 1 1
5 1 1
5 2 1
5 2 2
5 5 3
```
```output
NO
NO
YES
NO
YES
```

## Note
In the first test case, a ribbon consists of $$$1$$$ part. So all its parts will always have the same color.

In the second test case, there is only $$$1$$$ color.

In the third test case, Alice can paint the ribbon as follows: $$$[1, 2, 1, 2, 1]$$$. It's impossible to change the color of at most $$$1$$$ part so that all parts have the same color.

In the fourth test case, no matter how Alice paints the ribbon, Bob will always be able to repaint $$$2$$$ parts so that all parts have the same color.

In the fifth test case, Alice can paint the ribbon as follows: $$$[1, 2, 3, 4, 5]$$$. It's impossible to change the color of at most $$$3$$$ parts so that all parts have the same color.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call an array $$$a$$$ beautiful if you can make all its elements the same by using the following operation an arbitrary number of times (possibly, zero):

- choose an index $$$i$$$ ($$$2 \le i \le |a| - 1$$$) such that $$$a_{i - 1} = a_{i + 1}$$$, and replace $$$a_i$$$ with $$$a_{i - 1}$$$.

You are given a beautiful array $$$a_1, a_2, \dots, a_n$$$. What is the minimum number of elements you have to remove from it in order for it to stop being beautiful? Swapping elements is prohibited. If it is impossible to do so, then output -1.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Additional constraints on the input:

- in every test case, the given array $$$a$$$ is beautiful;
- the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the minimum number of elements you have to remove from the array $$$a$$$ in order for it to stop being beautiful. If it is impossible, then output -1.

## Examples
```input
4
3
2 2 2
5
1 2 1 2 1
1
1
7
3 3 3 5 3 3 3
```
```output
-1
1
-1
3
```

## Note
In the first testcase, it is impossible to modify the array in such a way that it stops being beautiful. An array consisting of identical numbers will remain beautiful no matter how many numbers we remove from it.

In the second testcase, you can remove the number at the index $$$5$$$, for example.

The resulting array will be $$$[1, 2, 1, 2]$$$. Let's check if it is beautiful. Two operations are available:

- Choose $$$i = 2$$$: the array becomes $$$[1, 1, 1, 2]$$$. No more operations can be applied to it, and the numbers are not all the same.
- Choose $$$i = 3$$$ instead: the array becomes $$$[1, 2, 2, 2]$$$. No more operations can be applied to it either, and the numbers are still not all the same.

Thus, the array $$$[1, 2, 1, 2]$$$ is not beautiful.

In the fourth testcase, you can remove the first three elements, for example. The resulting array $$$[5, 3, 3, 3]$$$ is not beautiful.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 1024.0 MB

# Problem
There are balls of $$$n$$$ different colors; the number of balls of the $$$i$$$-th color is $$$a_i$$$.

The balls can be combined into groups. Each group should contain at most $$$2$$$ balls, and no more than $$$1$$$ ball of each color.

Consider all $$$2^n$$$ sets of colors. For a set of colors, let's denote its value as the minimum number of groups the balls of those colors can be distributed into. For example, if there are three colors with $$$3$$$, $$$1$$$ and $$$7$$$ balls respectively, they can be combined into $$$7$$$ groups (and not less than $$$7$$$), so the value of that set of colors is $$$7$$$.

Your task is to calculate the sum of values over all $$$2^n$$$ possible sets of colors. Since the answer may be too large, print it modulo $$$998\,244\,353$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of colors.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5000$$$) — the number of balls of the $$$i$$$-th color.

Additional constraint on input: the total number of balls doesn't exceed $$$5000$$$.

## Output Format
Print a single integer — the sum of values of all $$$2^n$$$ sets of colors, taken modulo $$$998\,244\,353$$$.

## Examples
```input
3
1 1 2
```
```output
11
```
-----
```input
1
5
```
```output
5
```
-----
```input
4
1 3 3 7
```
```output
76
```

## Note
Consider the first example. There are $$$8$$$ sets of colors:

- for the empty set, its value is $$$0$$$;
- for the set $$$\{1\}$$$, its value is $$$1$$$;
- for the set $$$\{2\}$$$, its value is $$$1$$$;
- for the set $$$\{3\}$$$, its value is $$$2$$$;
- for the set $$$\{1,2\}$$$, its value is $$$1$$$;
- for the set $$$\{1,3\}$$$, its value is $$$2$$$;
- for the set $$$\{2,3\}$$$, its value is $$$2$$$;
- for the set $$$\{1,2,3\}$$$, its value is $$$2$$$.

So, the sum of values over all $$$2^n$$$ sets of colors is $$$11$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
There are $$$n$$$ monsters standing in a row. The $$$i$$$-th monster has $$$a_i$$$ health points.

Every second, you can choose one alive monster and launch a chain lightning at it. The lightning deals $$$k$$$ damage to it, and also spreads to the left (towards decreasing $$$i$$$) and to the right (towards increasing $$$i$$$) to alive monsters, dealing $$$k$$$ damage to each. When the lightning reaches a dead monster or the beginning/end of the row, it stops. A monster is considered alive if its health points are strictly greater than $$$0$$$.

For example, consider the following scenario: there are three monsters with health equal to $$$[5, 2, 7]$$$, and $$$k = 3$$$. You can kill them all in $$$4$$$ seconds:

- launch a chain lightning at the $$$3$$$-rd monster, then their health values are $$$[2, -1, 4]$$$;
- launch a chain lightning at the $$$1$$$-st monster, then their health values are $$$[-1, -1, 4]$$$;
- launch a chain lightning at the $$$3$$$-rd monster, then their health values are $$$[-1, -1, 1]$$$;
- launch a chain lightning at the $$$3$$$-th monster, then their health values are $$$[-1, -1, -2]$$$.

For each $$$k$$$ from $$$1$$$ to $$$\max(a_1, a_2, \dots, a_n)$$$, calculate the minimum number of seconds it takes to kill all the monsters.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of monsters.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the health points of the $$$i$$$-th monster.

## Output Format
For each $$$k$$$ from $$$1$$$ to $$$\max(a_1, a_2, \dots, a_n)$$$, output the minimum number of seconds it takes to kill all the monsters.

## Examples
```input
3
5 2 7
```
```output
10 6 4 3 2 2 1
```
-----
```input
4
7 7 7 7
```
```output
7 4 3 2 2 2 1
```
-----
```input
10
1 9 7 6 2 4 7 8 1 3
```
```output
17 9 5 4 3 3 3 2 1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's say that two strings $$$a$$$ and $$$b$$$ are equal if you can get the string $$$b$$$ by cyclically shifting string $$$a$$$. For example, the strings 0100110 and 1100100 are equal, while 1010 and 1100 are not.

You are given a binary string $$$s$$$ of length $$$n$$$. Its first $$$c$$$ characters are 1-s, and its last $$$n - c$$$ characters are 0-s.

In one operation, you can replace one 0 with 1.

Calculate the number of unique strings you can get using no more than $$$k$$$ operations. Since the answer may be too large, print it modulo $$$10^9 + 7$$$.

## Input Format
The first and only line contains three integers $$$n$$$, $$$c$$$ and $$$k$$$ ($$$1 \le n \le 3000$$$; $$$1 \le c \le n$$$; $$$0 \le k \le n - c$$$) — the length of string $$$s$$$, the length of prefix of 1-s and the maximum number of operations.

## Output Format
Print the single integer — the number of unique strings you can achieve performing no more than $$$k$$$ operations, modulo $$$10^9 + 7$$$.

## Examples
```input
1 1 0
```
```output
1
```
-----
```input
3 1 2
```
```output
3
```
-----
```input
5 1 1
```
```output
3
```
-----
```input
6 2 2
```
```output
7
```
-----
```input
24 3 11
```
```output
498062
```

## Note
In the first test case, the only possible string is 1.

In the second test case, the possible strings are: 100, 110, and 111. String 101 is equal to 110, so we don't count it.

In the third test case, the possible strings are: 10000, 11000, 10100. String 10010 is equal to 10100, and 10001 is equal to 11000.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You have been asked to organize a very important art conference. The first step is to choose the dates.

The conference must last for a certain number of consecutive days. Each day, one lecturer must perform, and the same lecturer cannot perform more than once.

You asked $$$n$$$ potential lecturers if they could participate in the conference. Lecturer $$$i$$$ indicated that they could perform on any day from $$$l_i$$$ to $$$r_i$$$ inclusive.

A certain segment of days can be chosen as the conference dates if there is a way to assign an available lecturer to each day of the segment, assigning each lecturer to no more than one day.

For each $$$k$$$ from $$$1$$$ to $$$n$$$, find how many ways there are to choose a segment of $$$k$$$ consecutive days as the conference dates.

## Input Format
The first line of input contains one integer $$$n$$$ — the number of potential lecturers ($$$1 \le n \le 2 \cdot 10^5$$$).

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ — the segment of available days for the $$$i$$$th lecturer ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$).

## Output Format
Print $$$n$$$ integers, where the $$$k$$$th number denotes the number of ways to select a segment of $$$k$$$ consecutive days as conference dates.

## Examples
```input
3
1 2
3 4
5 6
```
```output
6
2
0
```
-----
```input
5
1 3
1 3
1 3
1 3
1 3
```
```output
3
2
1
0
0
```

## Note
In the first testcase, a one-day conference can be organized on any of the days from $$$1$$$ to $$$6$$$. A two-day conference can be organized from day $$$2$$$ to day $$$3$$$, as well as from day $$$4$$$ to day $$$5$$$.

In the second testcase, five lecturers can perform only from day $$$1$$$ to day $$$3$$$, so it will not be possible to organize a conference longer than three days.

Now solve the problem and return the code.