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
Cucumber boy is fan of Kyubeat, a famous music game.

Kyubeat has 16 panels for playing arranged in 4 × 4 table. When a panel lights up, he has to press that panel.

Each panel has a timing to press (the preffered time when a player should press it), and Cucumber boy is able to press at most k panels in a time with his one hand. Cucumber boy is trying to press all panels in perfect timing, that is he wants to press each panel exactly in its preffered time. If he cannot press the panels with his two hands in perfect timing, his challenge to press all the panels in perfect timing will fail.

You are given one scene of Kyubeat's panel from the music Cucumber boy is trying. Tell him is he able to press all the panels in perfect timing.

## Input Format
The first line contains a single integer k (1 ≤ k ≤ 5) — the number of panels Cucumber boy can press with his one hand.

Next 4 lines contain 4 characters each (digits from 1 to 9, or period) — table of panels. If a digit i was written on the panel, it means the boy has to press that panel in time i. If period was written on the panel, he doesn't have to press that panel.

## Output Format
Output "YES" (without quotes), if he is able to press all the panels in perfect timing. If not, output "NO" (without quotes).

## Examples
```input
1
.135
1247
3468
5789
```
```output
YES
```
-----
```input
5
..1.
1111
..1.
..1.
```
```output
YES
```
-----
```input
1
....
12.1
.2..
.2..
```
```output
NO
```

## Note
In the third sample boy cannot press all panels in perfect timing. He can press all the panels in timing in time 1, but he cannot press the panels in time 2 in timing with his two hands.

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
We'll define S(n) for positive integer n as follows: the number of the n's digits in the decimal base. For example, S(893) = 3, S(114514) = 6.

You want to make a consecutive integer sequence starting from number m (m, m + 1, ...). But you need to pay S(n)·k to add the number n to the sequence.

You can spend a cost up to w, and you want to make the sequence as long as possible. Write a program that tells sequence's maximum length.

## Input Format
The first line contains three integers w (1 ≤ w ≤ 1016), m (1 ≤ m ≤ 1016), k (1 ≤ k ≤ 109).

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

## Output Format
The first line should contain a single integer — the answer to the problem.

## Examples
```input
9 1 1
```
```output
9
```
-----
```input
77 7 7
```
```output
7
```
-----
```input
114 5 14
```
```output
6
```
-----
```input
1 1 2
```
```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
Arthur and Alexander are number busters. Today they've got a competition.

Arthur took a group of four integers a, b, w, x (0 ≤ b < w, 0 < x < w) and Alexander took integer с. Arthur and Alexander use distinct approaches to number bustings. Alexander is just a regular guy. Each second, he subtracts one from his number. In other words, he performs the assignment: c = c - 1. Arthur is a sophisticated guy. Each second Arthur performs a complex operation, described as follows: if b ≥ x, perform the assignment b = b - x, if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b).

You've got numbers a, b, w, x, c. Determine when Alexander gets ahead of Arthur if both guys start performing the operations at the same time. Assume that Alexander got ahead of Arthur if c ≤ a.

## Input Format
The first line contains integers a, b, w, x, c (1 ≤ a ≤ 2·109, 1 ≤ w ≤ 1000, 0 ≤ b < w, 0 < x < w, 1 ≤ c ≤ 2·109).

## Output Format
Print a single integer — the minimum time in seconds Alexander needs to get ahead of Arthur. You can prove that the described situation always occurs within the problem's limits.

## Examples
```input
4 2 3 1 6
```
```output
2
```
-----
```input
4 2 3 1 7
```
```output
4
```
-----
```input
1 2 3 2 6
```
```output
13
```
-----
```input
1 1 2 1 1
```
```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
Everybody knows what an arithmetic progression is. Let us remind you just in case that an arithmetic progression is such sequence of numbers a1, a2, ..., an of length n, that the following condition fulfills:

a2 - a1 = a3 - a2 = a4 - a3 = ... = ai + 1 - ai = ... = an - an - 1.

For example, sequences [1, 5], [10], [5, 4, 3] are arithmetic progressions and sequences [1, 3, 2], [1, 2, 4] are not.

Alexander has n cards containing integers. Arthur wants to give Alexander exactly one more card with a number so that he could use the resulting n + 1 cards to make an arithmetic progression (Alexander has to use all of his cards).

Arthur has already bought a card but he hasn't written a number on it. Help him, print all integers that you can write on a card so that the described condition fulfilled.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — the number of cards. The next line contains the sequence of integers — the numbers on Alexander's cards. The numbers are positive integers, each of them doesn't exceed 108.

## Output Format
If Arthur can write infinitely many distinct integers on the card, print on a single line -1.

Otherwise, print on the first line the number of integers that suit you. In the second line, print the numbers in the increasing order. Note that the numbers in the answer can exceed 108 or even be negative (see test samples).

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

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
Ksenia has a chessboard of size n × m. Each cell of the chessboard contains one of the characters: "<", ">", "^", "v", "#". The cells that contain character "#" are blocked. We know that all chessboard cells that touch the border are blocked.

Ksenia is playing with two pawns on this chessboard. Initially, she puts the pawns on the chessboard. One cell of the chessboard can contain two pawns if and only if the cell is blocked. In other cases two pawns can not stand in one cell. The game begins when Ksenia put pawns on the board. In one move, Ksenia moves each pawn to a side adjacent cell in the direction of arrows painted on the cell on which the corresponding pawn sits (if the pawn sits on "#", it does not move). Assume that Ksenia moves pawns simultaneously (see the second test case).

Of course, Ksenia plays for points. How can one calculate the points per game? Very simply! Let's count how many movements the first pawn made and how many movements the second pawn made, sum these two numbers — it will be the resulting score of the game.

Ksenia wonders: what is the maximum number of points she can earn (for that, she should place the pawns optimally well early in the game). Help her and find that number.

## Input Format
The first line contains two integers, n and m (1 ≤ n, m ≤ 2000) — the sizes of the board. Each of the following n lines contains m characters – the board's description. Each character is one of the characters: "<", ">", "^", "v", "#".

It is guaranteed that the border cells of the table are blocked cells (with character "#").

## Output Format
If Ksenia can get infinitely many points, print -1. Otherwise, print the maximum number of points she can get.

## Examples
```input
1 1
#
```
```output
0
```
-----
```input
3 4
####
#>^#
####
```
```output
3
```
-----
```input
3 4
####
#><#
####
```
```output
-1
```
-----
```input
7 5
#####
##v##
##v##
#####
##^##
##^##
#####
```
```output
4
```
-----
```input
7 5
#####
##v##
##v##
##<##
##^##
##^##
#####
```
```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
Ksenia has her winter exams. Today she is learning combinatorics. Here's one of the problems she needs to learn to solve.

How many distinct trees are there consisting of n vertices, each with the following properties:

- the tree is marked, that is, the vertices of the tree are numbered from 1 to n;
- each vertex of the tree is connected with at most three other vertices, and at the same moment the vertex with number 1 is connected with at most two other vertices;
- the size of the tree's maximum matching equals k.

Two trees are considered distinct if there are such two vertices u and v, that in one tree they are connected by an edge and in the other tree they are not.

Help Ksenia solve the problem for the given n and k. As the answer to the problem can be very huge you should output it modulo 1000000007 (109 + 7).

## Input Format
The first line contains two integers n, k (1 ≤ n, k ≤ 50).

## Output Format
Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

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

## Note
If you aren't familiar with matchings, please, read the following link: http://en.wikipedia.org/wiki/Matching_(graph_theory).

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
George woke up and saw the current time s on the digital clock. Besides, George knows that he has slept for time t.

Help George! Write a program that will, given time s and t, determine the time p when George went to bed. Note that George could have gone to bed yesterday relatively to the current time (see the second test sample).

## Input Format
The first line contains current time s as a string in the format "hh:mm". The second line contains time t in the format "hh:mm" — the duration of George's sleep. It is guaranteed that the input contains the correct time in the 24-hour format, that is, 00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59.

## Output Format
In the single line print time p — the time George went to bed in the format similar to the format of the time in the input.

## Examples
```input
05:50
05:44
```
```output
00:06
```
-----
```input
00:00
01:00
```
```output
23:00
```
-----
```input
00:01
00:00
```
```output
00:01
```

## Note
In the first sample George went to bed at "00:06". Note that you should print the time only in the format "00:06". That's why answers "0:06", "00:6" and others will be considered incorrect.

In the second sample, George went to bed yesterday.

In the third sample, George didn't do to bed at all.

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
George is a cat, so he really likes to play. Most of all he likes to play with his array of positive integers b. During the game, George modifies the array by using special changes. Let's mark George's current array as b1, b2, ..., b|b| (record |b| denotes the current length of the array). Then one change is a sequence of actions:

- Choose two distinct indexes i and j (1 ≤ i, j ≤ |b|; i ≠ j), such that bi ≥ bj.
- Get number v = concat(bi, bj), where concat(x, y) is a number obtained by adding number y to the end of the decimal record of number x. For example, concat(500, 10) = 50010, concat(2, 2) = 22.
- Add number v to the end of the array. The length of the array will increase by one.
- Remove from the array numbers with indexes i and j. The length of the array will decrease by two, and elements of the array will become re-numbered from 1 to current length of the array.

George played for a long time with his array b and received from array b an array consisting of exactly one number p. Now George wants to know: what is the maximum number of elements array b could contain originally? Help him find this number. Note that originally the array could contain only positive integers.

## Input Format
The first line of the input contains a single integer p (1 ≤ p < 10100000). It is guaranteed that number p doesn't contain any leading zeroes.

## Output Format
Print an integer — the maximum number of elements array b could contain originally.

## Examples
```input
9555
```
```output
4
```
-----
```input
10000000005
```
```output
2
```
-----
```input
800101
```
```output
3
```
-----
```input
45
```
```output
1
```
-----
```input
1000000000000001223300003342220044555
```
```output
17
```
-----
```input
19992000
```
```output
1
```
-----
```input
310200
```
```output
2
```

## Note
Let's consider the test examples:

- Originally array b can be equal to {5, 9, 5, 5}. The sequence of George's changes could have been: {5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}.
- Originally array b could be equal to {1000000000, 5}. Please note that the array b cannot contain zeros.
- Originally array b could be equal to {800, 10, 1}.
- Originally array b could be equal to {45}. It cannot be equal to {4, 5}, because George can get only array {54} from this array in one operation.

Note that the numbers can be very large.

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
George loves graphs. Most of all, he loves interesting graphs. We will assume that a directed graph is interesting, if it meets the following criteria:

- The graph doesn't contain any multiple arcs;
- There is vertex v (we'll call her the center), such that for any vertex of graph u, the graph contains arcs (u, v) and (v, u). Please note that the graph also contains loop (v, v).
- The outdegree of all vertexes except for the center equals two and the indegree of all vertexes except for the center equals two. The outdegree of vertex u is the number of arcs that go out of u, the indegree of vertex u is the number of arcs that go in u. Please note that the graph can contain loops.

However, not everything's that simple. George got a directed graph of n vertices and m arcs as a present. The graph didn't have any multiple arcs. As George loves interesting graphs, he wants to slightly alter the presented graph and transform it into an interesting one. In one alteration he can either remove an arbitrary existing arc from the graph or add an arbitrary arc to the graph.

George wonders: what is the minimum number of changes that he needs to obtain an interesting graph from the graph he's got as a present? Help George and find the answer to the question.

## Input Format
The first line contains two space-separated integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 1000) — the number of vertices and arcs in the presented graph.

Each of the next m lines contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ n) — the descriptions of the graph's arcs. Pair (ai, bi) means that the graph contains an arc from vertex number ai to vertex number bi. It is guaranteed that the presented graph doesn't contain multiple arcs.

Assume that the grah vertices are numbered 1 through n.

## Output Format
Print a single integer — the answer to George's question.

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

## Note
For more information about directed graphs, please visit: http://en.wikipedia.org/wiki/Directed_graph

In the first sample the graph already is interesting, its center is vertex 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
Not so long ago company R2 bought company R1 and consequently, all its developments in the field of multicore processors. Now the R2 laboratory is testing one of the R1 processors.

The testing goes in n steps, at each step the processor gets some instructions, and then its temperature is measured. The head engineer in R2 is keeping a report record on the work of the processor: he writes down the minimum and the maximum measured temperature in his notebook. His assistant had to write down all temperatures into his notebook, but (for unknown reasons) he recorded only m.

The next day, the engineer's assistant filed in a report with all the m temperatures. However, the chief engineer doubts that the assistant wrote down everything correctly (naturally, the chief engineer doesn't doubt his notes). So he asked you to help him. Given numbers n, m, min, max and the list of m temperatures determine whether you can upgrade the set of m temperatures to the set of n temperatures (that is add n - m temperatures), so that the minimum temperature was min and the maximum one was max.

## Input Format
The first line contains four integers n, m, min, max (1 ≤ m < n ≤ 100; 1 ≤ min < max ≤ 100). The second line contains m space-separated integers ti (1 ≤ ti ≤ 100) — the temperatures reported by the assistant.

Note, that the reported temperatures, and the temperatures you want to add can contain equal temperatures.

## Output Format
If the data is consistent, print 'Correct' (without the quotes). Otherwise, print 'Incorrect' (without the quotes).

## Examples
```input
2 1 1 2
1
```
```output
Correct
```
-----
```input
3 1 1 3
2
```
```output
Correct
```
-----
```input
2 1 1 3
2
```
```output
Incorrect
```

## Note
In the first test sample one of the possible initial configurations of temperatures is [1, 2].

In the second test sample one of the possible initial configurations of temperatures is [2, 1, 3].

In the third test sample it is impossible to add one temperature to obtain the minimum equal to 1 and the maximum equal to 3.

Now solve the problem and return the code.