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 python3.

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:
```python
<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 python3.

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:
```python
<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.
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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string of length $$$n$$$. Each character is one of the first $$$p$$$ lowercase Latin letters.

You are also given a matrix $$$A$$$ with binary values of size $$$p \times p$$$. This matrix is symmetric ($$$A_{ij} = A_{ji}$$$). $$$A_{ij} = 1$$$ means that the string can have the $$$i$$$-th and $$$j$$$-th letters of Latin alphabet adjacent.

Let's call the string crisp if all of the adjacent characters in it can be adjacent (have 1 in the corresponding cell of matrix $$$A$$$).

You are allowed to do the following move. Choose any letter, remove all its occurrences and join the remaining parts of the string without changing their order. For example, removing letter 'a' from "abacaba" will yield "bcb".

The string you are given is crisp. The string should remain crisp after every move you make.

You are allowed to do arbitrary number of moves (possible zero). What is the shortest resulting string you can obtain?

## Input Format
The first line contains two integers $$$n$$$ and $$$p$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le p \le 17$$$) — the length of the initial string and the length of the allowed prefix of Latin alphabet.

The second line contains the initial string. It is guaranteed that it contains only first $$$p$$$ lowercase Latin letters and that is it crisp. Some of these $$$p$$$ first Latin letters might not be present in the string.

Each of the next $$$p$$$ lines contains $$$p$$$ integer numbers — the matrix $$$A$$$ ($$$0 \le A_{ij} \le 1$$$, $$$A_{ij} = A_{ji}$$$). $$$A_{ij} = 1$$$ means that the string can have the $$$i$$$-th and $$$j$$$-th letters of Latin alphabet adjacent.

## Output Format
Print a single integer — the length of the shortest string after you make arbitrary number of moves (possible zero).

## Examples
```input
7 3
abacaba
0 1 1
1 0 0
1 0 0
```
```output
7
```
-----
```input
7 3
abacaba
1 1 1
1 0 0
1 0 0
```
```output
0
```
-----
```input
7 4
bacadab
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
```
```output
5
```
-----
```input
3 3
cbc
0 0 0
0 0 1
0 1 0
```
```output
0
```

## Note
In the first example no letter can be removed from the initial string.

In the second example you can remove letters in order: 'b', 'c', 'a'. The strings on the intermediate steps will be: "abacaba" $$$\rightarrow$$$ "aacaa" $$$\rightarrow$$$ "aaaa" $$$\rightarrow$$$ "".

In the third example you can remove letter 'b' and that's it.

In the fourth example you can remove letters in order 'c', 'b', but not in the order 'b', 'c' because two letters 'c' can't be adjacent.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n$$$. Your task is to find some non-zero integer $$$d$$$ ($$$-10^3 \leq d \leq 10^3$$$) such that, after each number in the array is divided by $$$d$$$, the number of positive numbers that are presented in the array is greater than or equal to half of the array size (i.e., at least $$$\lceil\frac{n}{2}\rceil$$$). Note that those positive numbers do not need to be an integer (e.g., a $$$2.5$$$ counts as a positive number). If there are multiple values of $$$d$$$ that satisfy the condition, you may print any of them. In case that there is no such $$$d$$$, print a single integer $$$0$$$.

Recall that $$$\lceil x \rceil$$$ represents the smallest integer that is not less than $$$x$$$ and that zero ($$$0$$$) is neither positive nor negative.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in the array.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^3 \le a_i \le 10^3$$$).

## Output Format
Print one integer $$$d$$$ ($$$-10^3 \leq d \leq 10^3$$$ and $$$d \neq 0$$$) that satisfies the given condition. If there are multiple values of $$$d$$$ that satisfy the condition, you may print any of them. In case that there is no such $$$d$$$, print a single integer $$$0$$$.

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

## Note
In the first sample, $$$n = 5$$$, so we need at least $$$\lceil\frac{5}{2}\rceil = 3$$$ positive numbers after division. If $$$d = 4$$$, the array after division is $$$[2.5, 0, -1.75, 0.5, 1.5]$$$, in which there are $$$3$$$ positive numbers (namely: $$$2.5$$$, $$$0.5$$$, and $$$1.5$$$).

In the second sample, there is no valid $$$d$$$, so $$$0$$$ should be printed.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ivan recently bought a detective book. The book is so interesting that each page of this book introduces some sort of a mystery, which will be explained later. The $$$i$$$-th page contains some mystery that will be explained on page $$$a_i$$$ ($$$a_i \ge i$$$).

Ivan wants to read the whole book. Each day, he reads the first page he didn't read earlier, and continues to read the following pages one by one, until all the mysteries he read about are explained and clear to him (Ivan stops if there does not exist any page $$$i$$$ such that Ivan already has read it, but hasn't read page $$$a_i$$$). After that, he closes the book and continues to read it on the following day from the next page.

How many days will it take to read the whole book?

## Input Format
The first line contains single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the number of pages in the book.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$i \le a_i \le n$$$), where $$$a_i$$$ is the number of page which contains the explanation of the mystery on page $$$i$$$.

## Output Format
Print one integer — the number of days it will take to read the whole book.

## Examples
```input
9
1 3 3 6 7 6 8 8 9
```
```output
4
```

## Note
Explanation of the example test:

During the first day Ivan will read only the first page. During the second day Ivan will read pages number $$$2$$$ and $$$3$$$. During the third day — pages $$$4$$$-$$$8$$$. During the fourth (and the last) day Ivan will read remaining page number $$$9$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have a string $$$s$$$ of length $$$n$$$ consisting of only characters > and <. You may do some operations with this string, for each operation you have to choose some character that still remains in the string. If you choose a character >, the character that comes right after it is deleted (if the character you chose was the last one, nothing happens). If you choose a character <, the character that comes right before it is deleted (if the character you chose was the first one, nothing happens).

For example, if we choose character > in string > > < >, the string will become to > > >. And if we choose character < in string > <, the string will become to <.

The string is good if there is a sequence of operations such that after performing it only one character will remain in the string. For example, the strings >, > > are good.

Before applying the operations, you may remove any number of characters from the given string (possibly none, possibly up to $$$n - 1$$$, but not the whole string). You need to calculate the minimum number of characters to be deleted from string $$$s$$$ so that it becomes good.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) – the number of test cases. Each test case is represented by two lines.

The first line of $$$i$$$-th test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) – the length of string $$$s$$$.

The second line of $$$i$$$-th test case contains string $$$s$$$, consisting of only characters > and <.

## Output Format
For each test case print one line.

For $$$i$$$-th test case print the minimum number of characters to be deleted from string $$$s$$$ so that it becomes good.

## Examples
```input
3
2
<>
3
><<
1
>
```
```output
1
0
0
```

## Note
In the first test case we can delete any character in string <>.

In the second test case we don't need to delete any characters. The string > < < is good, because we can perform the following sequence of operations: > < < $$$\rightarrow$$$ < < $$$\rightarrow$$$ <.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You have a playlist consisting of $$$n$$$ songs. The $$$i$$$-th song is characterized by two numbers $$$t_i$$$ and $$$b_i$$$ — its length and beauty respectively. The pleasure of listening to set of songs is equal to the total length of the songs in the set multiplied by the minimum beauty among them. For example, the pleasure of listening to a set of $$$3$$$ songs having lengths $$$[5, 7, 4]$$$ and beauty values $$$[11, 14, 6]$$$ is equal to $$$(5 + 7 + 4) \cdot 6 = 96$$$.

You need to choose at most $$$k$$$ songs from your playlist, so the pleasure of listening to the set of these songs them is maximum possible.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) – the number of songs in the playlist and the maximum number of songs you can choose, respectively.

Each of the next $$$n$$$ lines contains two integers $$$t_i$$$ and $$$b_i$$$ ($$$1 \le t_i, b_i \le 10^6$$$) — the length and beauty of $$$i$$$-th song.

## Output Format
Print one integer — the maximum pleasure you can get.

## Examples
```input
4 3
4 7
15 1
3 6
6 8
```
```output
78
```
-----
```input
5 3
12 31
112 4
100 100
13 55
55 50
```
```output
10000
```

## Note
In the first test case we can choose songs $$${1, 3, 4}$$$, so the total pleasure is $$$(4 + 3 + 6) \cdot 6 = 78$$$.

In the second test case we can choose song $$$3$$$. The total pleasure will be equal to $$$100 \cdot 100 = 10000$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a regular polygon with $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$ in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there is no pair of triangles such that their intersection has non-zero area, and the total area of all triangles is equal to the area of the given polygon. The weight of a triangulation is the sum of weigths of triangles it consists of, where the weight of a triagle is denoted as the product of labels of its vertices.

Calculate the minimum weight among all triangulations of the polygon.

## Input Format
The first line contains single integer $$$n$$$ ($$$3 \le n \le 500$$$) — the number of vertices in the regular polygon.

## Output Format
Print one integer — the minimum weight among all triangulations of the given polygon.

## Examples
```input
3
```
```output
6
```
-----
```input
4
```
```output
18
```

## Note
According to Wiki: polygon triangulation is the decomposition of a polygonal area (simple polygon) $$$P$$$ into a set of triangles, i. e., finding a set of triangles with pairwise non-intersecting interiors whose union is $$$P$$$.

In the first example the polygon is a triangle, so we don't need to cut it further, so the answer is $$$1 \cdot 2 \cdot 3 = 6$$$.

In the second example the polygon is a rectangle, so it should be divided into two triangles. It's optimal to cut it using diagonal $$$1-3$$$ so answer is $$$1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's denote that some array $$$b$$$ is bad if it contains a subarray $$$b_l, b_{l+1}, \dots, b_{r}$$$ of odd length more than $$$1$$$ ($$$l < r$$$ and $$$r - l + 1$$$ is odd) such that $$$\forall i \in \{0, 1, \dots, r - l\}$$$ $$$b_{l + i} = b_{r - i}$$$.

If an array is not bad, it is good.

Now you are given an array $$$a_1, a_2, \dots, a_n$$$. Some elements are replaced by $$$-1$$$. Calculate the number of good arrays you can obtain by replacing each $$$-1$$$ with some integer from $$$1$$$ to $$$k$$$.

Since the answer can be large, print it modulo $$$998244353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n, k \le 2 \cdot 10^5$$$) — the length of array $$$a$$$ and the size of "alphabet", i. e., the upper bound on the numbers you may use to replace $$$-1$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i = -1$$$ or $$$1 \le a_i \le k$$$) — the array $$$a$$$.

## Output Format
Print one integer — the number of good arrays you can get, modulo $$$998244353$$$.

## Examples
```input
2 3
-1 -1
```
```output
9
```
-----
```input
5 2
1 -1 -1 1 2
```
```output
0
```
-----
```input
5 3
1 -1 -1 1 2
```
```output
2
```
-----
```input
4 200000
-1 -1 12345 -1
```
```output
735945883
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.5 seconds
Memory limit: 1024.0 MB

# Problem
For a given set of two-dimensional points $$$S$$$, let's denote its extension $$$E(S)$$$ as the result of the following algorithm:

Create another set of two-dimensional points $$$R$$$, which is initially equal to $$$S$$$. Then, while there exist four numbers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ such that $$$(x_1, y_1) \in R$$$, $$$(x_1, y_2) \in R$$$, $$$(x_2, y_1) \in R$$$ and $$$(x_2, y_2) \notin R$$$, add $$$(x_2, y_2)$$$ to $$$R$$$. When it is impossible to find such four integers, let $$$R$$$ be the result of the algorithm.

Now for the problem itself. You are given a set of two-dimensional points $$$S$$$, which is initially empty. You have to process two types of queries: add some point to $$$S$$$, or remove some point from it. After each query you have to compute the size of $$$E(S)$$$.

## Input Format
The first line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, each containing two integers $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le 3 \cdot 10^5$$$), denoting $$$i$$$-th query as follows: if $$$(x_i, y_i) \in S$$$, erase it from $$$S$$$, otherwise insert $$$(x_i, y_i)$$$ into $$$S$$$.

## Output Format
Print $$$q$$$ integers. $$$i$$$-th integer should be equal to the size of $$$E(S)$$$ after processing first $$$i$$$ queries.

## Examples
```input
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
```
```output
1 2 4 4 4 6 3
```

Now solve the problem and return the code.