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

# Problem
You are given a set of $$$n$$$ points in a 2D plane. No three points are collinear.

A pentagram is a set of $$$5$$$ points $$$A,B,C,D,E$$$ that can be arranged as follows.  Note the length of the line segments don't matter, only that those particular intersections exist.

Count the number of ways to choose $$$5$$$ points from the given set that form a pentagram.

## Input Format
The first line contains an integer $$$n$$$ ($$$5 \leq n \leq 300$$$) — the number of points.

Each of the next $$$n$$$ lines contains two integers $$$x_i, y_i$$$ ($$$-10^6 \leq x_i,y_i \leq 10^6$$$) — the coordinates of the $$$i$$$-th point. It is guaranteed that no three points are collinear.

## Output Format
Print a single integer, the number of sets of $$$5$$$ points that form a pentagram.

## Examples
```input
5
0 0
0 2
2 0
2 2
1 3
```
```output
1
```
-----
```input
5
0 0
4 0
0 4
4 4
2 3
```
```output
0
```
-----
```input
10
841746 527518
595261 331297
-946901 129987
670374 -140388
-684770 309555
-302589 415564
-387435 613331
-624940 -95922
945847 -199224
24636 -565799
```
```output
85
```

## Note
A picture of the first sample:  A picture of the second sample:  A picture of the third 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
Let's write all the positive integer numbers one after another from $$$1$$$ without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...

Your task is to print the $$$k$$$-th digit of this sequence.

## Input Format
The first and only line contains integer $$$k$$$ ($$$1 \le k \le 10000$$$) — the position to process ($$$1$$$-based index).

## Output Format
Print the $$$k$$$-th digit of the resulting infinite sequence.

## Examples
```input
7
```
```output
7
```
-----
```input
21
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let's write all the positive integer numbers one after another from $$$1$$$ without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...

Your task is to print the $$$k$$$-th digit of this sequence.

## Input Format
The first and only line contains integer $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — the position to process ($$$1$$$-based index).

## Output Format
Print the $$$k$$$-th digit of the resulting infinite sequence.

## Examples
```input
7
```
```output
7
```
-----
```input
21
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp knows that if the sum of the digits of a number is divisible by $$$3$$$, then the number itself is divisible by $$$3$$$. He assumes that the numbers, the sum of the digits of which is divisible by $$$4$$$, are also somewhat interesting. Thus, he considers a positive integer $$$n$$$ interesting if its sum of digits is divisible by $$$4$$$.

Help Polycarp find the nearest larger or equal interesting number for the given number $$$a$$$. That is, find the interesting number $$$n$$$ such that $$$n \ge a$$$ and $$$n$$$ is minimal.

## Input Format
The only line in the input contains an integer $$$a$$$ ($$$1 \le a \le 1000$$$).

## Output Format
Print the nearest greater or equal interesting number for the given number $$$a$$$. In other words, print the interesting number $$$n$$$ such that $$$n \ge a$$$ and $$$n$$$ is minimal.

## Examples
```input
432
```
```output
435
```
-----
```input
99
```
```output
103
```
-----
```input
237
```
```output
237
```
-----
```input
42
```
```output
44
```

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
This problem is actually a subproblem of problem G from the same contest.

There are $$$n$$$ candies in a candy box. The type of the $$$i$$$-th candy is $$$a_i$$$ ($$$1 \le a_i \le n$$$).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type $$$1$$$ and two candies of type $$$2$$$ is bad).

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

Your task is to find out the maximum possible size of the single gift you can prepare using the candies you have.

You have to answer $$$q$$$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries. Each query is represented by two lines.

The first line of each query contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of candies.

The second line of each query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the type of the $$$i$$$-th candy in the box.

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

## Output Format
For each query print one integer — the maximum possible size of the single gift you can compose using candies you got in this query with the restriction described in the problem statement.

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

## Note
In the first query, you can prepare a gift with two candies of type $$$8$$$ and one candy of type $$$5$$$, totalling to $$$3$$$ candies.

Note that this is not the only possible solution — taking two candies of type $$$4$$$ and one candy of type $$$6$$$ is also valid.

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

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string "abaca" the following strings are subsequences: "abaca", "aba", "aaa", "a" and "" (empty string). But the following strings are not subsequences: "aabaca", "cb" and "bcaa".

You are given a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

In one move you can take any subsequence $$$t$$$ of the given string and add it to the set $$$S$$$. The set $$$S$$$ can't contain duplicates. This move costs $$$n - |t|$$$, where $$$|t|$$$ is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).

Your task is to find out the minimum possible total cost to obtain a set $$$S$$$ of size $$$k$$$ or report that it is impossible to do so.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 100$$$) — the length of the string and the size of the set, correspondingly.

The second line of the input contains a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

## Output Format
Print one integer — if it is impossible to obtain the set $$$S$$$ of size $$$k$$$, print -1. Otherwise, print the minimum possible total cost to do it.

## Examples
```input
4 5
asdf
```
```output
4
```
-----
```input
5 6
aaaaa
```
```output
15
```
-----
```input
5 7
aaaaa
```
```output
-1
```
-----
```input
10 100
ajihiushda
```
```output
233
```

## Note
In the first example we can generate $$$S$$$ = { "asdf", "asd", "adf", "asf", "sdf" }. The cost of the first element in $$$S$$$ is $$$0$$$ and the cost of the others is $$$1$$$. So the total cost of $$$S$$$ is $$$4$$$.

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
One important contest will take place on the most famous programming platform (Topforces) very soon!

The authors have a pool of $$$n$$$ problems and should choose at most three of them into this contest. The prettiness of the $$$i$$$-th problem is $$$a_i$$$. The authors have to compose the most pretty contest (in other words, the cumulative prettinesses of chosen problems should be maximum possible).

But there is one important thing in the contest preparation: because of some superstitions of authors, the prettinesses of problems cannot divide each other. In other words, if the prettinesses of chosen problems are $$$x, y, z$$$, then $$$x$$$ should be divisible by neither $$$y$$$, nor $$$z$$$, $$$y$$$ should be divisible by neither $$$x$$$, nor $$$z$$$ and $$$z$$$ should be divisible by neither $$$x$$$, nor $$$y$$$. If the prettinesses of chosen problems are $$$x$$$ and $$$y$$$ then neither $$$x$$$ should be divisible by $$$y$$$ nor $$$y$$$ should be divisible by $$$x$$$. Any contest composed from one problem is considered good.

Your task is to find out the maximum possible total prettiness of the contest composed of at most three problems from the given pool.

You have to answer $$$q$$$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

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

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of problems.

The second line of the query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the prettiness of the $$$i$$$-th problem.

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

## Output Format
For each query print one integer — the maximum possible cumulative prettiness of the contest composed of at most three problems from the given pool of problems in the query.

## Examples
```input
3
4
5 6 15 30
4
10 6 30 15
3
3 4 6
```
```output
30
31
10
```

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

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string "abaca" the following strings are subsequences: "abaca", "aba", "aaa", "a" and "" (empty string). But the following strings are not subsequences: "aabaca", "cb" and "bcaa".

You are given a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

In one move you can take any subsequence $$$t$$$ of the given string and add it to the set $$$S$$$. The set $$$S$$$ can't contain duplicates. This move costs $$$n - |t|$$$, where $$$|t|$$$ is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).

Your task is to find out the minimum possible total cost to obtain a set $$$S$$$ of size $$$k$$$ or report that it is impossible to do so.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100, 1 \le k \le 10^{12}$$$) — the length of the string and the size of the set, correspondingly.

The second line of the input contains a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

## Output Format
Print one integer — if it is impossible to obtain the set $$$S$$$ of size $$$k$$$, print -1. Otherwise, print the minimum possible total cost to do it.

## Examples
```input
4 5
asdf
```
```output
4
```
-----
```input
5 6
aaaaa
```
```output
15
```
-----
```input
5 7
aaaaa
```
```output
-1
```
-----
```input
10 100
ajihiushda
```
```output
233
```

## Note
In the first example we can generate $$$S$$$ = { "asdf", "asd", "adf", "asf", "sdf" }. The cost of the first element in $$$S$$$ is $$$0$$$ and the cost of the others is $$$1$$$. So the total cost of $$$S$$$ is $$$4$$$.

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
Vus the Cossack holds a programming competition, in which $$$n$$$ people participate. He decided to award them all with pens and notebooks. It is known that Vus has exactly $$$m$$$ pens and $$$k$$$ notebooks.

Determine whether the Cossack can reward all participants, giving each of them at least one pen and at least one notebook.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m, k \leq 100$$$) — the number of participants, the number of pens, and the number of notebooks respectively.

## Output Format
Print "Yes" if it possible to reward all the participants. Otherwise, print "No".

You can print each letter in any case (upper or lower).

## Examples
```input
5 8 6
```
```output
Yes
```
-----
```input
3 9 3
```
```output
Yes
```
-----
```input
8 5 20
```
```output
No
```

## Note
In the first example, there are $$$5$$$ participants. The Cossack has $$$8$$$ pens and $$$6$$$ notebooks. Therefore, he has enough pens and notebooks.

In the second example, there are $$$3$$$ participants. The Cossack has $$$9$$$ pens and $$$3$$$ notebooks. He has more than enough pens but only the minimum needed number of notebooks.

In the third example, there are $$$8$$$ participants but only $$$5$$$ pens. Since the Cossack does not have enough pens, the answer is "No".

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
Vus the Cossack has $$$n$$$ real numbers $$$a_i$$$. It is known that the sum of all numbers is equal to $$$0$$$. He wants to choose a sequence $$$b$$$ the size of which is $$$n$$$ such that the sum of all numbers is $$$0$$$ and each $$$b_i$$$ is either $$$\lfloor a_i \rfloor$$$ or $$$\lceil a_i \rceil$$$. In other words, $$$b_i$$$ equals $$$a_i$$$ rounded up or down. It is not necessary to round to the nearest integer.

For example, if $$$a = [4.58413, 1.22491, -2.10517, -3.70387]$$$, then $$$b$$$ can be equal, for example, to $$$[4, 2, -2, -4]$$$.

Note that if $$$a_i$$$ is an integer, then there is no difference between $$$\lfloor a_i \rfloor$$$ and $$$\lceil a_i \rceil$$$, $$$b_i$$$ will always be equal to $$$a_i$$$.

Help Vus the Cossack find such sequence!

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of numbers.

Each of the next $$$n$$$ lines contains one real number $$$a_i$$$ ($$$|a_i| < 10^5$$$). It is guaranteed that each $$$a_i$$$ has exactly $$$5$$$ digits after the decimal point. It is guaranteed that the sum of all the numbers is equal to $$$0$$$.

## Output Format
In each of the next $$$n$$$ lines, print one integer $$$b_i$$$. For each $$$i$$$, $$$|a_i-b_i|<1$$$ must be met.

If there are multiple answers, print any.

## Examples
```input
4
4.58413
1.22491
-2.10517
-3.70387
```
```output
4
2
-2
-4
```
-----
```input
5
-6.32509
3.30066
-0.93878
2.00000
1.96321
```
```output
-6
3
-1
2
2
```

## Note
The first example is explained in the legend.

In the second example, we can round the first and fifth numbers up, and the second and third numbers down. We can round the fourth number neither up, nor down.

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

# Problem
Vus the Cossack has a simple graph with $$$n$$$ vertices and $$$m$$$ edges. Let $$$d_i$$$ be a degree of the $$$i$$$-th vertex. Recall that a degree of the $$$i$$$-th vertex is the number of conected edges to the $$$i$$$-th vertex.

He needs to remain not more than $$$\lceil \frac{n+m}{2} \rceil$$$ edges. Let $$$f_i$$$ be the degree of the $$$i$$$-th vertex after removing. He needs to delete them in such way so that $$$\lceil \frac{d_i}{2} \rceil \leq f_i$$$ for each $$$i$$$. In other words, the degree of each vertex should not be reduced more than twice.

Help Vus to remain the needed edges!

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^6$$$, $$$0 \leq m \leq 10^6$$$) — the number of vertices and edges respectively.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — vertices between which there is an edge.

It is guaranteed that the graph does not have loops and multiple edges.

It is possible to show that the answer always exists.

## Output Format
In the first line, print one integer $$$k$$$ ($$$0 \leq k \leq \lceil \frac{n+m}{2} \rceil$$$) — the number of edges which you need to remain.

In each of the next $$$k$$$ lines, print two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — the vertices, the edge between which, you need to remain. You can not print the same edge more than once.

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

Now solve the problem and return the code.