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

# Problem
Let $$$c$$$ be some positive integer. Let's call an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers $$$c$$$-array, if for all $$$i$$$ condition $$$1 \leq a_i \leq c$$$ is satisfied. Let's call $$$c$$$-array $$$b_1, b_2, \ldots, b_k$$$ a subarray of $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$, if there exists such set of $$$k$$$ indices $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ that $$$b_j = a_{i_j}$$$ for all $$$1 \leq j \leq k$$$. Let's define density of $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$ as maximal non-negative integer $$$p$$$, such that any $$$c$$$-array, that contains $$$p$$$ numbers is a subarray of $$$a_1, a_2, \ldots, a_n$$$.

You are given a number $$$c$$$ and some $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$. For all $$$0 \leq p \leq n$$$ find the number of sequences of indices $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ for all $$$1 \leq k \leq n$$$, such that density of array $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ is equal to $$$p$$$. Find these numbers by modulo $$$998\,244\,353$$$, because they can be too large.

## Input Format
The first line contains two integers $$$n$$$ and $$$c$$$, separated by spaces ($$$1 \leq n, c \leq 3\,000$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, separated by spaces ($$$1 \leq a_i \leq c$$$).

## Output Format
Print $$$n + 1$$$ numbers $$$s_0, s_1, \ldots, s_n$$$. $$$s_p$$$ should be equal to the number of sequences of indices $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ for all $$$1 \leq k \leq n$$$ by modulo $$$998\,244\,353$$$, such that the density of array $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ is equal to $$$p$$$.

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

## Note
In the first example, it's easy to see that the density of array will always be equal to its length. There exists $$$4$$$ sequences with one index, $$$6$$$ with two indices, $$$4$$$ with three and $$$1$$$ with four.

In the second example, the only sequence of indices, such that the array will have non-zero density is all indices because in other cases there won't be at least one number from $$$1$$$ to $$$3$$$ in the array, so it won't satisfy the condition of density for $$$p \geq 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a huge decimal number consisting of $$$n$$$ digits. It is guaranteed that this number has no leading zeros. Each digit of this number is either 0 or 1.

You may perform several (possibly zero) operations with this number. During each operation you are allowed to change any digit of your number; you may change 0 to 1 or 1 to 0. It is possible that after some operation you can obtain a number with leading zeroes, but it does not matter for this problem.

You are also given two integers $$$0 \le y < x < n$$$. Your task is to calculate the minimum number of operations you should perform to obtain the number that has remainder $$$10^y$$$ modulo $$$10^x$$$. In other words, the obtained number should have remainder $$$10^y$$$ when divided by $$$10^x$$$.

## Input Format
The first line of the input contains three integers $$$n, x, y$$$ ($$$0 \le y < x < n \le 2 \cdot 10^5$$$) — the length of the number and the integers $$$x$$$ and $$$y$$$, respectively.

The second line of the input contains one decimal number consisting of $$$n$$$ digits, each digit of this number is either 0 or 1. It is guaranteed that the first digit of the number is 1.

## Output Format
Print one integer — the minimum number of operations you should perform to obtain the number having remainder $$$10^y$$$ modulo $$$10^x$$$. In other words, the obtained number should have remainder $$$10^y$$$ when divided by $$$10^x$$$.

## Examples
```input
11 5 2
11010100101
```
```output
1
```
-----
```input
11 5 1
11010100101
```
```output
3
```

## Note
In the first example the number will be $$$11010100100$$$ after performing one operation. It has remainder $$$100$$$ modulo $$$100000$$$.

In the second example the number will be $$$11010100010$$$ after performing three operations. It has remainder $$$10$$$ modulo $$$100000$$$.

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
Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly $$$1$$$ problem, during the second day — exactly $$$2$$$ problems, during the third day — exactly $$$3$$$ problems, and so on. During the $$$k$$$-th day he should solve $$$k$$$ problems.

Polycarp has a list of $$$n$$$ contests, the $$$i$$$-th contest consists of $$$a_i$$$ problems. During each day Polycarp has to choose exactly one of the contests he didn't solve yet and solve it. He solves exactly $$$k$$$ problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least $$$k$$$ problems that Polycarp didn't solve yet during the $$$k$$$-th day, then Polycarp stops his training.

How many days Polycarp can train if he chooses the contests optimally?

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

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the number of problems in the $$$i$$$-th contest.

## Output Format
Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.

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

Now solve the problem and return the code.