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
Vector Willman and Array Bolt are the two most famous athletes of Byteforces. They are going to compete in a race with a distance of L meters today.

Willman and Bolt have exactly the same speed, so when they compete the result is always a tie. That is a problem for the organizers because they want a winner.

While watching previous races the organizers have noticed that Willman can perform only steps of length equal to w meters, and Bolt can perform only steps of length equal to b meters. Organizers decided to slightly change the rules of the race. Now, at the end of the racetrack there will be an abyss, and the winner will be declared the athlete, who manages to run farther from the starting point of the the racetrack (which is not the subject to change by any of the athletes).

Note that none of the athletes can run infinitely far, as they both will at some moment of time face the point, such that only one step further will cause them to fall in the abyss. In other words, the athlete will not fall into the abyss if the total length of all his steps will be less or equal to the chosen distance L.

Since the organizers are very fair, the are going to set the length of the racetrack as an integer chosen randomly and uniformly in range from 1 to t (both are included). What is the probability that Willman and Bolt tie again today?

## Input Format
The first line of the input contains three integers t, w and b (1 ≤ t, w, b ≤ 5·1018) — the maximum possible length of the racetrack, the length of Willman's steps and the length of Bolt's steps respectively.

## Output Format
Print the answer to the problem as an irreducible fraction $$\frac{p}{q}$$. Follow the format of the samples output.

The fraction $$\frac{p}{q}$$ (p and q are integers, and both p ≥ 0 and q > 0 holds) is called irreducible, if there is no such integer d > 1, that both p and q are divisible by d.

## Examples
```input
10 3 2
```
```output
3/10
```
-----
```input
7 1 2
```
```output
3/7
```

## Note
In the first sample Willman and Bolt will tie in case 1, 6 or 7 are chosen as the length of the racetrack.

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
Ari the monster is not an ordinary monster. She is the hidden identity of Super M, the Byteforces’ superhero. Byteforces is a country that consists of n cities, connected by n - 1 bidirectional roads. Every road connects exactly two distinct cities, and the whole road system is designed in a way that one is able to go from any city to any other city using only the given roads. There are m cities being attacked by humans. So Ari... we meant Super M have to immediately go to each of the cities being attacked to scare those bad humans. Super M can pass from one city to another only using the given roads. Moreover, passing through one road takes her exactly one kron - the time unit used in Byteforces.

However, Super M is not on Byteforces now - she is attending a training camp located in a nearby country Codeforces. Fortunately, there is a special device in Codeforces that allows her to instantly teleport from Codeforces to any city of Byteforces. The way back is too long, so for the purpose of this problem teleportation is used exactly once.

You are to help Super M, by calculating the city in which she should teleport at the beginning in order to end her job in the minimum time (measured in krons). Also, provide her with this time so she can plan her way back to Codeforces.

## Input Format
The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 123456) - the number of cities in Byteforces, and the number of cities being attacked respectively.

Then follow n - 1 lines, describing the road system. Each line contains two city numbers ui and vi (1 ≤ ui, vi ≤ n) - the ends of the road i.

The last line contains m distinct integers - numbers of cities being attacked. These numbers are given in no particular order.

## Output Format
First print the number of the city Super M should teleport to. If there are many possible optimal answers, print the one with the lowest city number.

Then print the minimum possible time needed to scare all humans in cities being attacked, measured in Krons.

Note that the correct answer is always unique.

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

## Note
In the first sample, there are two possibilities to finish the Super M's job in 3 krons. They are:

$$2 \rightarrow 1 \rightarrow 3 \rightarrow 7$$ and $$7 \rightarrow 3 \rightarrow 1 \rightarrow 2$$.

However, you should choose the first one as it starts in the city with the lower number.

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
After making bad dives into swimming pools, Wilbur wants to build a swimming pool in the shape of a rectangle in his backyard. He has set up coordinate axes, and he wants the sides of the rectangle to be parallel to them. Of course, the area of the rectangle must be positive. Wilbur had all four vertices of the planned pool written on a paper, until his friend came along and erased some of the vertices.

Now Wilbur is wondering, if the remaining n vertices of the initial rectangle give enough information to restore the area of the planned swimming pool.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 4) — the number of vertices that were not erased by Wilbur's friend.

Each of the following n lines contains two integers xi and yi ( - 1000 ≤ xi, yi ≤ 1000) —the coordinates of the i-th vertex that remains. Vertices are given in an arbitrary order.

It's guaranteed that these points are distinct vertices of some rectangle, that has positive area and which sides are parallel to the coordinate axes.

## Output Format
Print the area of the initial rectangle if it could be uniquely determined by the points remaining. Otherwise, print  - 1.

## Examples
```input
2
0 0
1 1
```
```output
1
```
-----
```input
1
1 1
```
```output
-1
```

## Note
In the first sample, two opposite corners of the initial rectangle are given, and that gives enough information to say that the rectangle is actually a unit square.

In the second sample there is only one vertex left and this is definitely not enough to uniquely define the area.

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
Wilbur the pig now wants to play with strings. He has found an n by m table consisting only of the digits from 0 to 9 where the rows are numbered 1 to n and the columns are numbered 1 to m. Wilbur starts at some square and makes certain moves. If he is at square (x, y) and the digit d (0 ≤ d ≤ 9) is written at position (x, y), then he must move to the square (x + ad, y + bd), if that square lies within the table, and he stays in the square (x, y) otherwise. Before Wilbur makes a move, he can choose whether or not to write the digit written in this square on the white board. All digits written on the whiteboard form some string. Every time a new digit is written, it goes to the end of the current string.

Wilbur has q strings that he is worried about. For each string si, Wilbur wants to know whether there exists a starting position (x, y) so that by making finitely many moves, Wilbur can end up with the string si written on the white board.

## Input Format
The first line of the input consists of three integers n, m, and q (1 ≤ n, m, q ≤ 200) — the dimensions of the table and the number of strings to process, respectively.

Each of the next n lines contains m digits from 0 and 9 giving the table itself.

Then follow 10 lines. The i-th of them contains the values ai - 1 and bi - 1 ( - 200 ≤ ai, bi ≤ 200), i.e. the vector that Wilbur uses to make a move from the square with a digit i - 1 in it.

There are q lines that follow. The i-th of them will contain a string si consisting only of digits from 0 to 9. It is guaranteed that the total length of these q strings won't exceed 1 000 000.

## Output Format
For each of the q strings, print "YES" if Wilbur can choose x and y in order to finish with this string after some finite number of moves. If it's impossible, than print "NO" for the corresponding string.

## Examples
```input
1 1 2
0
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
0000000000000
2413423432432
```
```output
YES
NO
```
-----
```input
4 2 5
01
23
45
67
0 1
0 -1
0 1
0 -1
0 1
0 -1
0 1
0 -1
0 1
0 -1
0000000000
010101011101
32232232322
44343222342444324
6767
```
```output
YES
YES
YES
NO
YES
```

## Note
In the first sample, there is a 1 by 1 table consisting of the only digit 0. The only move that can be made is staying on the square. The first string can be written on the white board by writing 0 repeatedly. The second string cannot be written as there is no 2 on the table.

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
Shapur was an extremely gifted student. He was great at everything including Combinatorics, Algebra, Number Theory, Geometry, Calculus, etc. He was not only smart but extraordinarily fast! He could manage to sum 1018 numbers in a single second.

One day in 230 AD Shapur was trying to find out if any one can possibly do calculations faster than him. As a result he made a very great contest and asked every one to come and take part.

In his contest he gave the contestants many different pairs of numbers. Each number is made from digits 0 or 1. The contestants should write a new number corresponding to the given pair of numbers. The rule is simple: The i-th digit of the answer is 1 if and only if the i-th digit of the two given numbers differ. In the other case the i-th digit of the answer is 0.

Shapur made many numbers and first tried his own speed. He saw that he can perform these operations on numbers of length ∞ (length of a number is number of digits in it) in a glance! He always gives correct answers so he expects the contestants to give correct answers, too. He is a good fellow so he won't give anyone very big numbers and he always gives one person numbers of same length.

Now you are going to take part in Shapur's contest. See if you are faster and more accurate.

## Input Format
There are two lines in each input. Each of them contains a single number. It is guaranteed that the numbers are made from 0 and 1 only and that their length is same. The numbers may start with 0. The length of each number doesn't exceed 100.

## Output Format
Write one line — the corresponding answer. Do not omit the leading 0s.

## Examples
```input
1010100
0100101
```
```output
1110001
```
-----
```input
000
111
```
```output
111
```
-----
```input
1110
1010
```
```output
0100
```
-----
```input
01110
01100
```
```output
00010
```

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
An elephant decided to visit his friend. It turned out that the elephant's house is located at point 0 and his friend's house is located at point x(x > 0) of the coordinate line. In one step the elephant can move 1, 2, 3, 4 or 5 positions forward. Determine, what is the minimum number of steps he need to make in order to get to his friend's house.

## Input Format
The first line of the input contains an integer x (1 ≤ x ≤ 1 000 000) — The coordinate of the friend's house.

## Output Format
Print the minimum number of steps that elephant needs to make to get from point 0 to point x.

## Examples
```input
5
```
```output
1
```
-----
```input
12
```
```output
3
```

## Note
In the first sample the elephant needs to make one step of length 5 to reach the point x.

In the second sample the elephant can get to point x if he moves by 3, 5 and 4. There are other ways to get the optimal answer but the elephant cannot reach x in less than three moves.

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
Bob loves everything sweet. His favorite chocolate bar consists of pieces, each piece may contain a nut. Bob wants to break the bar of chocolate into multiple pieces so that each part would contain exactly one nut and any break line goes between two adjacent pieces.

You are asked to calculate the number of ways he can do it. Two ways to break chocolate are considered distinct if one of them contains a break between some two adjacent pieces and the other one doesn't.

Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut.

## Input Format
The first line of the input contains integer n (1 ≤ n ≤ 100) — the number of pieces in the chocolate bar.

The second line contains n integers ai (0 ≤ ai ≤ 1), where 0 represents a piece without the nut and 1 stands for a piece with the nut.

## Output Format
Print the number of ways to break the chocolate into multiple parts so that each part would contain exactly one nut.

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

## Note
In the first sample there is exactly one nut, so the number of ways equals 1 — Bob shouldn't make any breaks.

In the second sample you can break the bar in four ways:

10|10|1

1|010|1

10|1|01

1|01|01

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
There are three points marked on the coordinate plane. The goal is to make a simple polyline, without self-intersections and self-touches, such that it passes through all these points. Also, the polyline must consist of only segments parallel to the coordinate axes. You are to find the minimum number of segments this polyline may consist of.

## Input Format
Each of the three lines of the input contains two integers. The i-th line contains integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th point. It is guaranteed that all points are distinct.

## Output Format
Print a single number — the minimum possible number of segments of the polyline.

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

## Note
The variant of the polyline in the first sample:  The variant of the polyline in the second sample:  The variant of the polyline in 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
Consider the infinite sequence of integers: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5.... The sequence is built in the following way: at first the number 1 is written out, then the numbers from 1 to 2, then the numbers from 1 to 3, then the numbers from 1 to 4 and so on. Note that the sequence contains numbers, not digits. For example number 10 first appears in the sequence in position 55 (the elements are numerated from one).

Find the number on the n-th position of the sequence.

## Input Format
The only line contains integer n (1 ≤ n ≤ 1014) — the position of the number to find.

Note that the given number is too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

## Output Format
Print the element in the n-th position of the sequence (the elements are numerated from one).

## Examples
```input
3
```
```output
2
```
-----
```input
5
```
```output
2
```
-----
```input
10
```
```output
4
```
-----
```input
55
```
```output
10
```
-----
```input
56
```
```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 the current time in 24-hour format hh:mm. Find and print the time after a minutes.

Note that you should find only the time after a minutes, see the examples to clarify the problem statement.

You can read more about 24-hour format here https://en.wikipedia.org/wiki/24-hour_clock.

## Input Format
The first line contains the current time in the format hh:mm (0 ≤ hh < 24, 0 ≤ mm < 60). The hours and the minutes are given with two digits (the hours or the minutes less than 10 are given with the leading zeroes).

The second line contains integer a (0 ≤ a ≤ 104) — the number of the minutes passed.

## Output Format
The only line should contain the time after a minutes in the format described in the input. Note that you should print exactly two digits for the hours and the minutes (add leading zeroes to the numbers if needed).

See the examples to check the input/output format.

## Examples
```input
23:59
10
```
```output
00:09
```
-----
```input
20:20
121
```
```output
22:21
```
-----
```input
10:10
0
```
```output
10: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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi.

For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the number of elements in a and the number of queries.

The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.

Each of the next m lines contains three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — the parameters of the i-th query.

## Output Format
Print m lines. On the i-th line print integer pi — the position of any number not equal to xi in segment [li, ri] or the value  - 1 if there is no such number.

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

Now solve the problem and return the code.