apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Nian is a monster which lives deep in the oceans. Once a year, it shows up on the land, devouring livestock and even people. In order to keep the monster away, people fill their villages with red colour, light, and cracking noise, all of which frighten the monster out of coming.

Little Tommy has n lanterns and Big Banban has m lanterns. Tommy's lanterns have brightness a1, a2, ..., an, and Banban's have brightness b1, b2, ..., bm respectively.

Tommy intends to hide one of his lanterns, then Banban picks one of Tommy's non-hidden lanterns and one of his own lanterns to form a pair. The pair's brightness will be the product of the brightness of two lanterns.

Tommy wants to make the product as small as possible, while Banban tries to make it as large as possible.

You are asked to find the brightness of the chosen pair if both of them choose optimally.

## Input Format
The first line contains two space-separated integers n and m (2 ≤ n, m ≤ 50).

The second line contains n space-separated integers a1, a2, ..., an.

The third line contains m space-separated integers b1, b2, ..., bm.

All the integers range from  - 109 to 109.

## Output Format
Print a single integer — the brightness of the chosen pair.

## Examples
```input
2 2
20 18
2 14
```
```output
252
```
-----
```input
5 3
-1 0 1 2 3
-1 0 1
```
```output
2
```

## Note
In the first example, Tommy will hide 20 and Banban will choose 18 from Tommy and 14 from himself.

In the second example, Tommy will hide 3 and Banban will choose 2 from Tommy and 1 from himself.

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
Apart from Nian, there is a daemon named Sui, which terrifies children and causes them to become sick. Parents give their children money wrapped in red packets and put them under the pillow, so that when Sui tries to approach them, it will be driven away by the fairies inside.

Big Banban is hesitating over the amount of money to give out. He considers loops to be lucky since it symbolizes unity and harmony.

He would like to find a positive integer n not greater than 1018, such that there are exactly k loops in the decimal representation of n, or determine that such n does not exist.

A loop is a planar area enclosed by lines in the digits' decimal representation written in Arabic numerals. For example, there is one loop in digit 4, two loops in 8 and no loops in 5. Refer to the figure below for all exact forms.

## Input Format
The first and only line contains an integer k (1 ≤ k ≤ 106) — the desired number of loops.

## Output Format
Output an integer — if no such n exists, output -1; otherwise output any such n. In the latter case, your output should be a positive decimal integer not exceeding 1018.

## Examples
```input
2
```
```output
462
```
-----
```input
6
```
```output
8080
```

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
Petya loves football very much. One day, as he was watching a football match, he was writing the players' current positions on a piece of paper. To simplify the situation he depicted it as a string consisting of zeroes and ones. A zero corresponds to players of one team; a one corresponds to players of another team. If there are at least 7 players of some team standing one after another, then the situation is considered dangerous. For example, the situation 00100110111111101 is dangerous and 11110111011101 is not. You are given the current situation. Determine whether it is dangerous or not.

## Input Format
The first input line contains a non-empty string consisting of characters "0" and "1", which represents players. The length of the string does not exceed 100 characters. There's at least one player from each team present on the field.

## Output Format
Print "YES" if the situation is dangerous. Otherwise, print "NO".

## Examples
```input
001001
```
```output
NO
```
-----
```input
1000000001
```
```output
YES
```

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
Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

One day Petya came across a positive integer n. Help him to find the least super lucky number which is not less than n.

## Input Format
The only line contains a positive integer n (1 ≤ n ≤ 109). This number doesn't have leading zeroes.

## Output Format
Output the least super lucky number that is more than or equal to n.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

## Examples
```input
4500
```
```output
4747
```
-----
```input
47
```
```output
47
```

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 created his own training plan to prepare for the programming contests. He will train for $$$n$$$ days, all days are numbered from $$$1$$$ to $$$n$$$, beginning from the first.

On the $$$i$$$-th day Polycarp will necessarily solve $$$a_i$$$ problems. One evening Polycarp plans to celebrate the equator. He will celebrate it on the first evening of such a day that from the beginning of the training and to this day inclusive he will solve half or more of all the problems.

Determine the index of day when Polycarp will celebrate the equator.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of days to prepare for the programming contests.

The second line contains a sequence $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10\,000$$$), where $$$a_i$$$ equals to the number of problems, which Polycarp will solve on the $$$i$$$-th day.

## Output Format
Print the index of the day when Polycarp will celebrate the equator.

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

## Note
In the first example Polycarp will celebrate the equator on the evening of the second day, because up to this day (inclusive) he will solve $$$4$$$ out of $$$7$$$ scheduled problems on four days of the training.

In the second example Polycarp will celebrate the equator on the evening of the third day, because up to this day (inclusive) he will solve $$$6$$$ out of $$$12$$$ scheduled problems on six days of the training.

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
There are $$$n$$$ consecutive seat places in a railway carriage. Each place is either empty or occupied by a passenger.

The university team for the Olympiad consists of $$$a$$$ student-programmers and $$$b$$$ student-athletes. Determine the largest number of students from all $$$a+b$$$ students, which you can put in the railway carriage so that:

- no student-programmer is sitting next to the student-programmer;
- and no student-athlete is sitting next to the student-athlete.

In the other words, there should not be two consecutive (adjacent) places where two student-athletes or two student-programmers are sitting.

Consider that initially occupied seat places are occupied by jury members (who obviously are not students at all).

## Input Format
The first line contain three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 2\cdot10^{5}$$$, $$$0 \le a, b \le 2\cdot10^{5}$$$, $$$a + b > 0$$$) — total number of seat places in the railway carriage, the number of student-programmers and the number of student-athletes.

The second line contains a string with length $$$n$$$, consisting of characters "." and "*". The dot means that the corresponding place is empty. The asterisk means that the corresponding place is occupied by the jury member.

## Output Format
Print the largest number of students, which you can put in the railway carriage so that no student-programmer is sitting next to a student-programmer and no student-athlete is sitting next to a student-athlete.

## Examples
```input
5 1 1
*...*
```
```output
2
```
-----
```input
6 2 3
*...*.
```
```output
4
```
-----
```input
11 3 10
.*....**.*.
```
```output
7
```
-----
```input
3 2 3
***
```
```output
0
```

## Note
In the first example you can put all student, for example, in the following way: *.AB*

In the second example you can put four students, for example, in the following way: *BAB*B

In the third example you can put seven students, for example, in the following way: B*ABAB**A*B

The letter A means a student-programmer, and the letter B — student-athlete.

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 positive integer $$$n$$$, written without leading zeroes (for example, the number 04 is incorrect).

In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.

Determine the minimum number of operations that you need to consistently apply to the given integer $$$n$$$ to make from it the square of some positive integer or report that it is impossible.

An integer $$$x$$$ is the square of some positive integer if and only if $$$x=y^2$$$ for some positive integer $$$y$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{9}$$$). The number is given without leading zeroes.

## Output Format
If it is impossible to make the square of some positive integer from $$$n$$$, print -1. In the other case, print the minimal number of operations required to do it.

## Examples
```input
8314
```
```output
2
```
-----
```input
625
```
```output
0
```
-----
```input
333
```
```output
-1
```

## Note
In the first example we should delete from $$$8314$$$ the digits $$$3$$$ and $$$4$$$. After that $$$8314$$$ become equals to $$$81$$$, which is the square of the integer $$$9$$$.

In the second example the given $$$625$$$ is the square of the integer $$$25$$$, so you should not delete anything.

In the third example it is impossible to make the square from $$$333$$$, so the answer 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges. The graph does not necessarily connected. Guaranteed, that the graph does not contain multiple edges (more than one edges between a pair of vertices) or loops (edges from a vertex to itself).

A cycle in a graph is called a simple, if it contains each own vertex exactly once. So simple cycle doesn't allow to visit a vertex more than once in a cycle.

Determine the edges, which belong to exactly on one simple cycle.

## Input Format
The first line contain two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 100\,000$$$, $$$0 \le m \le \min(n \cdot (n - 1) / 2, 100\,000))$$$ — the number of vertices and the number of edges.

Each of the following $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the description of the edges.

## Output Format
In the first line print the number of edges, which belong to exactly one simple cycle.

In the second line print the indices of edges, which belong to exactly one simple cycle, in increasing order. The edges are numbered from one in the same order as they are given in the input.

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

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
Petya has a polygon consisting of $$$n$$$ vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches. All internal area of the polygon (borders are not included) was painted in black color by Petya.

Also, Petya has a rectangular window, defined by its coordinates, through which he looks at the polygon. A rectangular window can not be moved. The sides of the rectangular window are parallel to the coordinate axes.

Blue color represents the border of a polygon, red color is the Petya's window. The answer in this case is 2.

Determine the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

## Input Format
The first line contain four integers $$$x_1, y_1, x_2, y_2$$$ ($$$x_1 < x_2$$$, $$$y_2 < y_1$$$) — the coordinates of top-left and bottom-right corners of the rectangular window.

The second line contains a single integer $$$n$$$ ($$$4 \le n \le 15\,000$$$) — the number of vertices in Petya's polygon.

Each of the following $$$n$$$ lines contains two integers — the coordinates of vertices of the Petya's polygon in counterclockwise order. Guaranteed, that the given polygon satisfies the conditions described in the statement.

All coordinates of the rectangular window and all coordinates of the vertices of the polygon are non-negative and do not exceed $$$15\,000$$$.

## Output Format
Print the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

## Examples
```input
5 7 16 3
16
0 0
18 0
18 6
16 6
16 1
10 1
10 4
7 4
7 2
2 2
2 6
12 6
12 12
10 12
10 8
0 8
```
```output
2
```

## Note
The example corresponds to the picture above.

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
These days Arkady works as an air traffic controller at a large airport. He controls a runway which is usually used for landings only. Thus, he has a schedule of planes that are landing in the nearest future, each landing lasts $$$1$$$ minute.

He was asked to insert one takeoff in the schedule. The takeoff takes $$$1$$$ minute itself, but for safety reasons there should be a time space between the takeoff and any landing of at least $$$s$$$ minutes from both sides.

Find the earliest time when Arkady can insert the takeoff.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 100$$$, $$$1 \le s \le 60$$$) — the number of landings on the schedule and the minimum allowed time (in minutes) between a landing and a takeoff.

Each of next $$$n$$$ lines contains two integers $$$h$$$ and $$$m$$$ ($$$0 \le h \le 23$$$, $$$0 \le m \le 59$$$) — the time, in hours and minutes, when a plane will land, starting from current moment (i. e. the current time is $$$0$$$ $$$0$$$). These times are given in increasing order.

## Output Format
Print two integers $$$h$$$ and $$$m$$$ — the hour and the minute from the current moment of the earliest time Arkady can insert the takeoff.

## Examples
```input
6 60
0 0
1 20
3 21
5 0
19 30
23 40
```
```output
6 1
```
-----
```input
16 50
0 30
1 20
3 0
4 30
6 10
7 50
9 30
11 10
12 50
14 30
16 10
17 50
19 30
21 10
22 50
23 59
```
```output
24 50
```
-----
```input
3 17
0 30
1 0
12 0
```
```output
0 0
```

## Note
In the first example note that there is not enough time between 1:20 and 3:21, because each landing and the takeoff take one minute.

In the second example there is no gaps in the schedule, so Arkady can only add takeoff after all landings. Note that it is possible that one should wait more than $$$24$$$ hours to insert the takeoff.

In the third example Arkady can insert the takeoff even between the first landing.

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
Nastya owns too many arrays now, so she wants to delete the least important of them. However, she discovered that this array is magic! Nastya now knows that the array has the following properties:

- In one second we can add an arbitrary (possibly negative) integer to all elements of the array that are not equal to zero.
- When all elements of the array become equal to zero, the array explodes.

Nastya is always busy, so she wants to explode the array as fast as possible. Compute the minimum time in which the array can be exploded.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 105) — the size of the array.

The second line contains n integers a1, a2, ..., an ( - 105 ≤ ai ≤ 105) — the elements of the array.

## Output Format
Print a single integer — the minimum number of seconds needed to make all elements of the array equal to zero.

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

## Note
In the first example you can add  - 1 to all non-zero elements in one second and make them equal to zero.

In the second example you can add  - 2 on the first second, then the array becomes equal to [0, 0,  - 3]. On the second second you can add 3 to the third (the only non-zero) element.

Now solve the problem and return the code.