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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$l$$$ and $$$r$$$ ($$$l \le r$$$). Your task is to calculate the sum of numbers from $$$l$$$ to $$$r$$$ (including $$$l$$$ and $$$r$$$) such that each number contains at most $$$k$$$ different digits, and print this sum modulo $$$998244353$$$.

For example, if $$$k = 1$$$ then you have to calculate all numbers from $$$l$$$ to $$$r$$$ such that each number is formed using only one digit. For $$$l = 10, r = 50$$$ the answer is $$$11 + 22 + 33 + 44 = 110$$$.

## Input Format
The only line of the input contains three integers $$$l$$$, $$$r$$$ and $$$k$$$ ($$$1 \le l \le r < 10^{18}, 1 \le k \le 10$$$) — the borders of the segment and the maximum number of different digits.

## Output Format
Print one integer — the sum of numbers from $$$l$$$ to $$$r$$$ such that each number contains at most $$$k$$$ different digits, modulo $$$998244353$$$.

## Examples
```input
10 50 2
```
```output
1230
```
-----
```input
1 2345 10
```
```output
2750685
```
-----
```input
101 154 2
```
```output
2189
```

## Note
For the first example the answer is just the sum of numbers from $$$l$$$ to $$$r$$$ which equals to $$$\frac{50 \cdot 51}{2} - \frac{9 \cdot 10}{2} = 1230$$$. This example also explained in the problem statement but for $$$k = 1$$$.

For the second example the answer is just the sum of numbers from $$$l$$$ to $$$r$$$ which equals to $$$\frac{2345 \cdot 2346}{2} = 2750685$$$.

For the third example the answer is $$$101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189$$$.

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 is a house with $$$n$$$ flats situated on the main street of Berlatov. Vova is watching this house every night. The house can be represented as an array of $$$n$$$ integer numbers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i = 1$$$ if in the $$$i$$$-th flat the light is on and $$$a_i = 0$$$ otherwise.

Vova thinks that people in the $$$i$$$-th flats are disturbed and cannot sleep if and only if $$$1 < i < n$$$ and $$$a_{i - 1} = a_{i + 1} = 1$$$ and $$$a_i = 0$$$.

Vova is concerned by the following question: what is the minimum number $$$k$$$ such that if people from exactly $$$k$$$ pairwise distinct flats will turn off the lights then nobody will be disturbed? Your task is to find this number $$$k$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of flats in the house.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{0, 1\}$$$), where $$$a_i$$$ is the state of light in the $$$i$$$-th flat.

## Output Format
Print only one integer — the minimum number $$$k$$$ such that if people from exactly $$$k$$$ pairwise distinct flats will turn off the light then nobody will be disturbed.

## Examples
```input
10
1 1 0 1 1 0 1 0 1 0
```
```output
2
```
-----
```input
5
1 1 0 0 0
```
```output
0
```
-----
```input
4
1 1 1 1
```
```output
0
```

## Note
In the first example people from flats $$$2$$$ and $$$7$$$ or $$$4$$$ and $$$7$$$ can turn off the light and nobody will be disturbed. It can be shown that there is no better answer in this example.

There are no disturbed people in second and third examples.

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
Polycarp has prepared $$$n$$$ competitive programming problems. The topic of the $$$i$$$-th problem is $$$a_i$$$, and some problems' topics may coincide.

Polycarp has to host several thematic contests. All problems in each contest should have the same topic, and all contests should have pairwise distinct topics. He may not use all the problems. It is possible that there are no contests for some topics.

Polycarp wants to host competitions on consecutive days, one contest per day. Polycarp wants to host a set of contests in such a way that:

- number of problems in each contest is exactly twice as much as in the previous contest (one day ago), the first contest can contain arbitrary number of problems;
- the total number of problems in all the contests should be maximized.

Your task is to calculate the maximum number of problems in the set of thematic contests. Note, that you should not maximize the number of contests.

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

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) where $$$a_i$$$ is the topic of the $$$i$$$-th problem.

## Output Format
Print one integer — the maximum number of problems in the set of thematic contests.

## Examples
```input
18
2 1 2 10 2 10 10 2 2 1 10 10 10 10 1 1 10 10
```
```output
14
```
-----
```input
10
6 6 6 3 6 1000000000 3 3 6 6
```
```output
9
```
-----
```input
3
1337 1337 1337
```
```output
3
```

## Note
In the first example the optimal sequence of contests is: $$$2$$$ problems of the topic $$$1$$$, $$$4$$$ problems of the topic $$$2$$$, $$$8$$$ problems of the topic $$$10$$$.

In the second example the optimal sequence of contests is: $$$3$$$ problems of the topic $$$3$$$, $$$6$$$ problems of the topic $$$6$$$.

In the third example you can take all the problems with the topic $$$1337$$$ (the number of such problems is $$$3$$$ so the answer is $$$3$$$) and host a single contest.

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
The only difference between easy and hard versions is the constraints.

Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of $$$n$$$ consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the $$$i$$$-th picture has beauty $$$a_i$$$.

Vova wants to repost exactly $$$x$$$ pictures in such a way that:

- each segment of the news feed of at least $$$k$$$ consecutive pictures has at least one picture reposted by Vova;
- the sum of beauty values of reposted pictures is maximum possible.

For example, if $$$k=1$$$ then Vova has to repost all the pictures in the news feed. If $$$k=2$$$ then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.

## Input Format
The first line of the input contains three integers $$$n, k$$$ and $$$x$$$ ($$$1 \le k, x \le n \le 200$$$) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the beauty of the $$$i$$$-th picture.

## Output Format
Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.

## Examples
```input
5 2 3
5 1 3 10 1
```
```output
18
```
-----
```input
6 1 5
10 30 30 70 10 10
```
```output
-1
```
-----
```input
4 3 1
1 100 1 1
```
```output
100
```

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.5 seconds
Memory limit: 512.0 MB

# Problem
The only difference between easy and hard versions is the constraints.

Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of $$$n$$$ consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the $$$i$$$-th picture has beauty $$$a_i$$$.

Vova wants to repost exactly $$$x$$$ pictures in such a way that:

- each segment of the news feed of at least $$$k$$$ consecutive pictures has at least one picture reposted by Vova;
- the sum of beauty values of reposted pictures is maximum possible.

For example, if $$$k=1$$$ then Vova has to repost all the pictures in the news feed. If $$$k=2$$$ then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.

## Input Format
The first line of the input contains three integers $$$n, k$$$ and $$$x$$$ ($$$1 \le k, x \le n \le 5000$$$) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the beauty of the $$$i$$$-th picture.

## Output Format
Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.

## Examples
```input
5 2 3
5 1 3 10 1
```
```output
18
```
-----
```input
6 1 5
10 30 30 70 10 10
```
```output
-1
```
-----
```input
4 3 1
1 100 1 1
```
```output
100
```

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
Sasha is a very happy guy, that's why he is always on the move. There are $$$n$$$ cities in the country where Sasha lives. They are all located on one straight line, and for convenience, they are numbered from $$$1$$$ to $$$n$$$ in increasing order. The distance between any two adjacent cities is equal to $$$1$$$ kilometer. Since all roads in the country are directed, it's possible to reach the city $$$y$$$ from the city $$$x$$$ only if $$$x < y$$$.

Once Sasha decided to go on a trip around the country and to visit all $$$n$$$ cities. He will move with the help of his car, Cheetah-2677. The tank capacity of this model is $$$v$$$ liters, and it spends exactly $$$1$$$ liter of fuel for $$$1$$$ kilometer of the way. At the beginning of the journey, the tank is empty. Sasha is located in the city with the number $$$1$$$ and wants to get to the city with the number $$$n$$$. There is a gas station in each city. In the $$$i$$$-th city, the price of $$$1$$$ liter of fuel is $$$i$$$ dollars. It is obvious that at any moment of time, the tank can contain at most $$$v$$$ liters of fuel.

Sasha doesn't like to waste money, that's why he wants to know what is the minimum amount of money is needed to finish the trip if he can buy fuel in any city he wants. Help him to figure it out!

## Input Format
The first line contains two integers $$$n$$$ and $$$v$$$ ($$$2 \le n \le 100$$$, $$$1 \le v \le 100$$$)  — the number of cities in the country and the capacity of the tank.

## Output Format
Print one integer — the minimum amount of money that is needed to finish the trip.

## Examples
```input
4 2
```
```output
4
```
-----
```input
7 6
```
```output
6
```

## Note
In the first example, Sasha can buy $$$2$$$ liters for $$$2$$$ dollars ($$$1$$$ dollar per liter) in the first city, drive to the second city, spend $$$1$$$ liter of fuel on it, then buy $$$1$$$ liter for $$$2$$$ dollars in the second city and then drive to the $$$4$$$-th city. Therefore, the answer is $$$1+1+2=4$$$.

In the second example, the capacity of the tank allows to fill the tank completely in the first city, and drive to the last city without stops in other cities.

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
One day Sasha visited the farmer 2D and his famous magnetic farm. On this farm, the crop grows due to the influence of a special magnetic field. Maintaining of the magnetic field is provided by $$$n$$$ machines, and the power of the $$$i$$$-th machine is $$$a_i$$$.

This year 2D decided to cultivate a new culture, but what exactly he didn't say. For the successful growth of the new culture, it is necessary to slightly change the powers of the machines. 2D can at most once choose an arbitrary integer $$$x$$$, then choose one machine and reduce the power of its machine by $$$x$$$ times, and at the same time increase the power of one another machine by $$$x$$$ times (powers of all the machines must stay positive integers). Note that he may not do that if he wants. More formally, 2D can choose two such indices $$$i$$$ and $$$j$$$, and one integer $$$x$$$ such that $$$x$$$ is a divisor of $$$a_i$$$, and change powers as following: $$$a_i = \frac{a_i}{x}$$$, $$$a_j = a_j \cdot x$$$

Sasha is very curious, that's why he wants to calculate the minimum total power the farmer can reach. There are too many machines, and Sasha can't cope with computations, help him!

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — the powers of the machines.

## Output Format
Print one integer — minimum total power.

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

## Note
In the first example, the farmer can reduce the power of the $$$4$$$-th machine by $$$2$$$ times, and increase the power of the $$$1$$$-st machine by $$$2$$$ times, then the powers will be: $$$[2, 2, 3, 2, 5]$$$.

In the second example, the farmer can reduce the power of the $$$3$$$-rd machine by $$$2$$$ times, and increase the power of the $$$2$$$-nd machine by $$$2$$$ times. At the same time, the farmer can leave is be as it is and the total power won't change.

In the third example, it is optimal to leave it be as it is.

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
You are given array $$$a_1, a_2, \dots, a_n$$$. Find the subsegment $$$a_l, a_{l+1}, \dots, a_r$$$ ($$$1 \le l \le r \le n$$$) with maximum arithmetic mean $$$\frac{1}{r - l + 1}\sum\limits_{i=l}^{r}{a_i}$$$ (in floating-point numbers, i.e. without any rounding).

If there are many such subsegments find the longest one.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array $$$a$$$.

## Output Format
Print the single integer — the length of the longest subsegment with maximum possible arithmetic mean.

## Examples
```input
5
6 1 6 6 0
```
```output
2
```

## Note
The subsegment $$$[3, 4]$$$ is the longest among all subsegments with maximum arithmetic mean.

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$$$ emotes in very popular digital collectible card game (the game is pretty famous so we won't say its name). The $$$i$$$-th emote increases the opponent's happiness by $$$a_i$$$ units (we all know that emotes in this game are used to make opponents happy).

You have time to use some emotes only $$$m$$$ times. You are allowed to use any emotion once, more than once, or not use it at all. The only restriction is that you cannot use the same emote more than $$$k$$$ times in a row (otherwise the opponent will think that you're trolling him).

Note that two emotes $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) such that $$$a_i = a_j$$$ are considered different.

You have to make your opponent as happy as possible. Find the maximum possible opponent's happiness.

## Input Format
The first line of the input contains three integers $$$n, m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le m \le 2 \cdot 10^9$$$) — the number of emotes, the number of times you can use emotes and the maximum number of times you may use the same emote in a row.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is value of the happiness of the $$$i$$$-th emote.

## Output Format
Print one integer — the maximum opponent's happiness if you use emotes in a way satisfying the problem statement.

## Examples
```input
6 9 2
1 3 3 7 4 2
```
```output
54
```
-----
```input
3 1000000000 1
1000000000 987654321 1000000000
```
```output
1000000000000000000
```

## Note
In the first example you may use emotes in the following sequence: $$$4, 4, 5, 4, 4, 5, 4, 4, 5$$$.

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: 256.0 MB

# Problem
Reziba has many magic gems. Each magic gem can be split into $$$M$$$ normal gems. The amount of space each magic (and normal) gem takes is $$$1$$$ unit. A normal gem cannot be split.

Reziba wants to choose a set of magic gems and split some of them, so the total space occupied by the resulting set of gems is $$$N$$$ units. If a magic gem is chosen and split, it takes $$$M$$$ units of space (since it is split into $$$M$$$ gems); if a magic gem is not split, it takes $$$1$$$ unit.

How many different configurations of the resulting set of gems can Reziba have, such that the total amount of space taken is $$$N$$$ units? Print the answer modulo $$$1000000007$$$ ($$$10^9+7$$$). Two configurations are considered different if the number of magic gems Reziba takes to form them differs, or the indices of gems Reziba has to split differ.

## Input Format
The input contains a single line consisting of $$$2$$$ integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 10^{18}$$$, $$$2 \le M \le 100$$$).

## Output Format
Print one integer, the total number of configurations of the resulting set of gems, given that the total amount of space taken is $$$N$$$ units. Print the answer modulo $$$1000000007$$$ ($$$10^9+7$$$).

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

## Note
In the first example each magic gem can split into $$$2$$$ normal gems, and we know that the total amount of gems are $$$4$$$.

Let $$$1$$$ denote a magic gem, and $$$0$$$ denote a normal gem.

The total configurations you can have is:

- $$$1 1 1 1$$$ (None of the gems split);
- $$$0 0 1 1$$$ (First magic gem splits into $$$2$$$ normal gems);
- $$$1 0 0 1$$$ (Second magic gem splits into $$$2$$$ normal gems);
- $$$1 1 0 0$$$ (Third magic gem splits into $$$2$$$ normal gems);
- $$$0 0 0 0$$$ (First and second magic gems split into total $$$4$$$ normal gems).

Hence, answer is $$$5$$$.

Now solve the problem and return the code.