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 an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex $$$a$$$ is connected with a vertex $$$b$$$, a vertex $$$b$$$ is also connected with a vertex $$$a$$$). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices $$$u$$$ and $$$v$$$ belong to the same connected component if and only if there is at least one path along edges connecting $$$u$$$ and $$$v$$$.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

- the first vertex is connected with the second vertex by an edge,
- the second vertex is connected with the third vertex by an edge,
- ...
- the last vertex is connected with the first vertex by an edge,
- all the described edges of a cycle are distinct.

A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.

There are $$$6$$$ connected components, $$$2$$$ of them are cycles: $$$[7, 10, 16]$$$ and $$$[5, 11, 9, 15]$$$.

## Input Format
The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — number of vertices and edges.

The following $$$m$$$ lines contains edges: edge $$$i$$$ is given as a pair of vertices $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$). There is no multiple edges in the given graph, i.e. for each pair ($$$v_i, u_i$$$) there no other pairs ($$$v_i, u_i$$$) and ($$$u_i, v_i$$$) in the list of edges.

## Output Format
Print one integer — the number of connected components which are also cycles.

## Examples
```input
5 4
1 2
3 4
5 4
3 5
```
```output
1
```
-----
```input
17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6
```
```output
2
```

## Note
In the first example only component $$$[3, 4, 5]$$$ is also a cycle.

The illustration above corresponds to the second example.

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 working as an analyst in a company working on a new system for big data storage. This system will store $$$n$$$ different objects. Each object should have a unique ID.

To create the system, you choose the parameters of the system — integers $$$m \ge 1$$$ and $$$b_{1}, b_{2}, \ldots, b_{m}$$$. With these parameters an ID of some object in the system is an array of integers $$$[a_{1}, a_{2}, \ldots, a_{m}]$$$ where $$$1 \le a_{i} \le b_{i}$$$ holds for every $$$1 \le i \le m$$$.

Developers say that production costs are proportional to $$$\sum_{i=1}^{m} b_{i}$$$. You are asked to choose parameters $$$m$$$ and $$$b_{i}$$$ so that the system will be able to assign unique IDs to $$$n$$$ different objects and production costs are minimized. Note that you don't have to use all available IDs.

## Input Format
In the only line of input there is one positive integer $$$n$$$. The length of the decimal representation of $$$n$$$ is no greater than $$$1.5 \cdot 10^{6}$$$. The integer does not contain leading zeros.

## Output Format
Print one number — minimal value of $$$\sum_{i=1}^{m} b_{i}$$$.

## Examples
```input
36
```
```output
10
```
-----
```input
37
```
```output
11
```
-----
```input
12345678901234567890123456789
```
```output
177
```

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 $$$n$$$ coins, the value of the $$$i$$$-th coin is $$$a_i$$$. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket.

For example, if Polycarp has got six coins represented as an array $$$a = [1, 2, 4, 3, 3, 2]$$$, he can distribute the coins into two pockets as follows: $$$[1, 2, 3], [2, 3, 4]$$$.

Polycarp wants to distribute all the coins with the minimum number of used pockets. Help him to do that.

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

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$) — values of coins.

## Output Format
Print only one integer — the minimum number of pockets Polycarp needs to distribute all the coins so no two coins with the same value are put into the same pocket.

## Examples
```input
6
1 2 4 3 3 2
```
```output
2
```
-----
```input
1
100
```
```output
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 three integers $$$a$$$, $$$b$$$ and $$$x$$$. Your task is to construct a binary string $$$s$$$ of length $$$n = a + b$$$ such that there are exactly $$$a$$$ zeroes, exactly $$$b$$$ ones and exactly $$$x$$$ indices $$$i$$$ (where $$$1 \le i < n$$$) such that $$$s_i \ne s_{i + 1}$$$. It is guaranteed that the answer always exists.

For example, for the string "01010" there are four indices $$$i$$$ such that $$$1 \le i < n$$$ and $$$s_i \ne s_{i + 1}$$$ ($$$i = 1, 2, 3, 4$$$). For the string "111001" there are two such indices $$$i$$$ ($$$i = 3, 5$$$).

Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.

## Input Format
The first line of the input contains three integers $$$a$$$, $$$b$$$ and $$$x$$$ ($$$1 \le a, b \le 100, 1 \le x < a + b)$$$.

## Output Format
Print only one string $$$s$$$, where $$$s$$$ is any binary string satisfying conditions described above. It is guaranteed that the answer always exists.

## Examples
```input
2 2 1
```
```output
1100
```
-----
```input
3 3 3
```
```output
101100
```
-----
```input
5 3 6
```
```output
01010100
```

## Note
All possible answers for the first example:

- 1100;
- 0011.

All possible answers for the second example:

- 110100;
- 101100;
- 110010;
- 100110;
- 011001;
- 001101;
- 010011;
- 001011.

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
The heat during the last few days has been really intense. Scientists from all over the Berland study how the temperatures and weather change, and they claim that this summer is abnormally hot. But any scientific claim sounds a lot more reasonable if there are some numbers involved, so they have decided to actually calculate some value which would represent how high the temperatures are.

Mathematicians of Berland State University came up with a special heat intensity value. This value is calculated as follows:

Suppose we want to analyze the segment of $$$n$$$ consecutive days. We have measured the temperatures during these $$$n$$$ days; the temperature during $$$i$$$-th day equals $$$a_i$$$.

We denote the average temperature of a segment of some consecutive days as the arithmetic mean of the temperature measures during this segment of days. So, if we want to analyze the average temperature from day $$$x$$$ to day $$$y$$$, we calculate it as $$$\frac{\sum \limits_{i = x}^{y} a_i}{y - x + 1}$$$ (note that division is performed without any rounding). The heat intensity value is the maximum of average temperatures over all segments of not less than $$$k$$$ consecutive days. For example, if analyzing the measures $$$[3, 4, 1, 2]$$$ and $$$k = 3$$$, we are interested in segments $$$[3, 4, 1]$$$, $$$[4, 1, 2]$$$ and $$$[3, 4, 1, 2]$$$ (we want to find the maximum value of average temperature over these segments).

You have been hired by Berland State University to write a program that would compute the heat intensity value of a given period of days. Are you up to this task?

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — the number of days in the given period, and the minimum number of days in a segment we consider when calculating heat intensity value, respectively.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 5000$$$) — the temperature measures during given $$$n$$$ days.

## Output Format
Print one real number — the heat intensity value, i. e., the maximum of average temperatures over all segments of not less than $$$k$$$ consecutive days.

Your answer will be considered correct if the following condition holds: $$$|res - res_0| < 10^{-6}$$$, where $$$res$$$ is your answer, and $$$res_0$$$ is the answer given by the jury's solution.

## Examples
```input
4 3
3 4 1 2
```
```output
2.666666666666667
```

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 has $$$n$$$ coins, the value of the $$$i$$$-th coin is $$$a_i$$$. It is guaranteed that all the values are integer powers of $$$2$$$ (i.e. $$$a_i = 2^d$$$ for some non-negative integer number $$$d$$$).

Polycarp wants to know answers on $$$q$$$ queries. The $$$j$$$-th query is described as integer number $$$b_j$$$. The answer to the query is the minimum number of coins that is necessary to obtain the value $$$b_j$$$ using some subset of coins (Polycarp can use only coins he has). If Polycarp can't obtain the value $$$b_j$$$, the answer to the $$$j$$$-th query is -1.

The queries are independent (the answer on the query doesn't affect Polycarp's coins).

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of coins and the number of queries.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ — values of coins ($$$1 \le a_i \le 2 \cdot 10^9$$$). It is guaranteed that all $$$a_i$$$ are integer powers of $$$2$$$ (i.e. $$$a_i = 2^d$$$ for some non-negative integer number $$$d$$$).

The next $$$q$$$ lines contain one integer each. The $$$j$$$-th line contains one integer $$$b_j$$$ — the value of the $$$j$$$-th query ($$$1 \le b_j \le 10^9$$$).

## Output Format
Print $$$q$$$ integers $$$ans_j$$$. The $$$j$$$-th integer must be equal to the answer on the $$$j$$$-th query. If Polycarp can't obtain the value $$$b_j$$$ the answer to the $$$j$$$-th query is -1.

## Examples
```input
5 4
2 4 8 2 4
8
5
14
10
```
```output
1
-1
3
2
```

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
You are given three integers $$$n$$$, $$$d$$$ and $$$k$$$.

Your task is to construct an undirected tree on $$$n$$$ vertices with diameter $$$d$$$ and degree of each vertex at most $$$k$$$, or say that it is impossible.

An undirected tree is a connected undirected graph with $$$n - 1$$$ edges.

Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree.

Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex $$$u$$$ it is the number of edges $$$(u, v)$$$ that belong to the tree, where $$$v$$$ is any other vertex of a tree).

## Input Format
The first line of the input contains three integers $$$n$$$, $$$d$$$ and $$$k$$$ ($$$1 \le n, d, k \le 4 \cdot 10^5$$$).

## Output Format
If there is no tree satisfying the conditions above, print only one word "NO" (without quotes).

Otherwise in the first line print "YES" (without quotes), and then print $$$n - 1$$$ lines describing edges of a tree satisfying the conditions above. Vertices of the tree must be numbered from $$$1$$$ to $$$n$$$. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.1

## Examples
```input
6 3 3
```
```output
YES
3 1
4 1
1 2
5 2
2 6
```
-----
```input
6 2 3
```
```output
NO
```
-----
```input
10 4 3
```
```output
YES
2 9
2 10
10 3
3 1
6 10
8 2
4 3
5 6
6 7
```
-----
```input
8 5 3
```
```output
YES
2 5
7 2
3 7
3 1
1 6
8 7
4 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a text consisting of $$$n$$$ space-separated words. There is exactly one space character between any pair of adjacent words. There are no spaces before the first word and no spaces after the last word. The length of text is the number of letters and spaces in it. $$$w_i$$$ is the $$$i$$$-th word of text. All words consist only of lowercase Latin letters.

Let's denote a segment of words $$$w[i..j]$$$ as a sequence of words $$$w_i, w_{i + 1}, \dots, w_j$$$. Two segments of words $$$w[i_1 .. j_1]$$$ and $$$w[i_2 .. j_2]$$$ are considered equal if $$$j_1 - i_1 = j_2 - i_2$$$, $$$j_1 \ge i_1$$$, $$$j_2 \ge i_2$$$, and for every $$$t \in [0, j_1 - i_1]$$$ $$$w_{i_1 + t} = w_{i_2 + t}$$$. For example, for the text "to be or not to be" the segments $$$w[1..2]$$$ and $$$w[5..6]$$$ are equal, they correspond to the words "to be".

An abbreviation is a replacement of some segments of words with their first uppercase letters. In order to perform an abbreviation, you have to choose at least two non-intersecting equal segments of words, and replace each chosen segment with the string consisting of first letters of the words in the segment (written in uppercase). For example, for the text "a ab a a b ab a a b c" you can replace segments of words $$$w[2..4]$$$ and $$$w[6..8]$$$ with an abbreviation "AAA" and obtain the text "a AAA b AAA b c", or you can replace segments of words $$$w[2..5]$$$ and $$$w[6..9]$$$ with an abbreviation "AAAB" and obtain the text "a AAAB AAAB c".

What is the minimum length of the text after at most one abbreviation?

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 300$$$) — the number of words in the text.

The next line contains $$$n$$$ space-separated words of the text $$$w_1, w_2, \dots, w_n$$$. Each word consists only of lowercase Latin letters.

It is guaranteed that the length of text does not exceed $$$10^5$$$.

## Output Format
Print one integer — the minimum length of the text after at most one abbreviation.

## Examples
```input
6
to be or not to be
```
```output
12
```
-----
```input
10
a ab a a b ab a a b c
```
```output
13
```
-----
```input
6
aa bb aa aa bb bb
```
```output
11
```

## Note
In the first example you can obtain the text "TB or not TB".

In the second example you can obtain the text "a AAAB AAAB c".

In the third example you can obtain the text "AB aa AB bb".

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
John Smith knows that his son, Thomas Smith, is among the best students in his class and even in his school. After the students of the school took the exams in English, German, Math, and History, a table of results was formed.

There are $$$n$$$ students, each of them has a unique id (from $$$1$$$ to $$$n$$$). Thomas's id is $$$1$$$. Every student has four scores correspond to his or her English, German, Math, and History scores. The students are given in order of increasing of their ids.

In the table, the students will be sorted by decreasing the sum of their scores. So, a student with the largest sum will get the first place. If two or more students have the same sum, these students will be sorted by increasing their ids.

Please help John find out the rank of his son.

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

Each of the next $$$n$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$0\leq a_i, b_i, c_i, d_i\leq 100$$$) — the grades of the $$$i$$$-th student on English, German, Math, and History. The id of the $$$i$$$-th student is equal to $$$i$$$.

## Output Format
Print the rank of Thomas Smith. Thomas's id is $$$1$$$.

## Examples
```input
5
100 98 100 100
100 100 100 100
100 100 99 99
90 99 90 100
100 98 60 99
```
```output
2
```
-----
```input
6
100 80 90 99
60 60 60 60
90 60 100 60
60 100 60 80
100 100 0 100
0 0 0 0
```
```output
1
```

## Note
In the first sample, the students got total scores: $$$398$$$, $$$400$$$, $$$398$$$, $$$379$$$, and $$$357$$$. Among the $$$5$$$ students, Thomas and the third student have the second highest score, but Thomas has a smaller id, so his rank is $$$2$$$.

In the second sample, the students got total scores: $$$369$$$, $$$240$$$, $$$310$$$, $$$300$$$, $$$300$$$, and $$$0$$$. Among the $$$6$$$ students, Thomas got the highest score, so his rank is $$$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
Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secret phone number!

The only thing Mrs. Smith remembered was that any permutation of $$$n$$$ can be a secret phone number. Only those permutations that minimize secret value might be the phone of her husband.

The sequence of $$$n$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once.

The secret value of a phone number is defined as the sum of the length of the longest increasing subsequence (LIS) and length of the longest decreasing subsequence (LDS).

A subsequence $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ where $$$1\leq i_1 < i_2 < \ldots < i_k\leq n$$$ is called increasing if $$$a_{i_1} < a_{i_2} < a_{i_3} < \ldots < a_{i_k}$$$. If $$$a_{i_1} > a_{i_2} > a_{i_3} > \ldots > a_{i_k}$$$, a subsequence is called decreasing. An increasing/decreasing subsequence is called longest if it has maximum length among all increasing/decreasing subsequences.

For example, if there is a permutation $$$[6, 4, 1, 7, 2, 3, 5]$$$, LIS of this permutation will be $$$[1, 2, 3, 5]$$$, so the length of LIS is equal to $$$4$$$. LDS can be $$$[6, 4, 1]$$$, $$$[6, 4, 2]$$$, or $$$[6, 4, 3]$$$, so the length of LDS is $$$3$$$.

Note, the lengths of LIS and LDS can be different.

So please help Mrs. Smith to find a permutation that gives a minimum sum of lengths of LIS and LDS.

## Input Format
The only line contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of permutation that you need to build.

## Output Format
Print a permutation that gives a minimum sum of lengths of LIS and LDS.

If there are multiple answers, print any.

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

## Note
In the first sample, you can build a permutation $$$[3, 4, 1, 2]$$$. LIS is $$$[3, 4]$$$ (or $$$[1, 2]$$$), so the length of LIS is equal to $$$2$$$. LDS can be ony of $$$[3, 1]$$$, $$$[4, 2]$$$, $$$[3, 2]$$$, or $$$[4, 1]$$$. The length of LDS is also equal to $$$2$$$. The sum is equal to $$$4$$$. Note that $$$[3, 4, 1, 2]$$$ is not the only permutation that is valid.

In the second sample, you can build a permutation $$$[2, 1]$$$. LIS is $$$[1]$$$ (or $$$[2]$$$), so the length of LIS is equal to $$$1$$$. LDS is $$$[2, 1]$$$, so the length of LDS is equal to $$$2$$$. The sum is equal to $$$3$$$. Note that permutation $$$[1, 2]$$$ is also valid.

Now solve the problem and return the code.