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 python3.

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:
```python
<your code here>
```

Execution time limit: 6.0 seconds
Memory limit: 256.0 MB

# Problem
Long time ago, there was a great kingdom and it was being ruled by The Great Arya and Pari The Great. These two had some problems about the numbers they like, so they decided to divide the great kingdom between themselves.

The great kingdom consisted of n cities numbered from 1 to n and m bidirectional roads between these cities, numbered from 1 to m. The i-th road had length equal to wi. The Great Arya and Pari The Great were discussing about destructing some prefix (all road with numbers less than some x) and suffix (all roads with numbers greater than some x) of the roads so there will remain only the roads with numbers l, l + 1, ..., r - 1 and r.

After that they will divide the great kingdom into two pieces (with each city belonging to exactly one piece) such that the hardness of the division is minimized. The hardness of a division is the maximum length of a road such that its both endpoints are in the same piece of the kingdom. In case there is no such road, the hardness of the division is considered to be equal to  - 1.

Historians found the map of the great kingdom, and they have q guesses about the l and r chosen by those great rulers. Given these data, for each guess li and ri print the minimum possible hardness of the division of the kingdom.

## Input Format
The first line of the input contains three integers n, m and q (1 ≤ n, q ≤ 1000, $$1 \leq m \leq \frac{n \times (n-1)}{2}$$) — the number of cities and roads in the great kingdom, and the number of guesses, respectively.

The i-th line of the following m lines contains three integers ui, vi and wi (1  ≤  ui,  vi  ≤  n, 0 ≤ wi ≤ 109), denoting the road number i connects cities ui and vi and its length is equal wi. It's guaranteed that no road connects the city to itself and no pair of cities is connected by more than one road.

Each of the next q lines contains a pair of integers li and ri (1  ≤ li ≤ ri ≤ m) — a guess from the historians about the remaining roads in the kingdom.

## Output Format
For each guess print the minimum possible hardness of the division in described scenario.

## Examples
```input
5 6 5
5 4 86
5 1 0
1 3 38
2 1 33
2 4 28
2 3 40
3 5
2 6
1 3
2 3
1 6
```
```output
-1
33
-1
-1
33
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Today Pari gave Arya a cool graph problem. Arya wrote a non-optimal solution for it, because he believes in his ability to optimize non-optimal solutions. In addition to being non-optimal, his code was buggy and he tried a lot to optimize it, so the code also became dirty! He keeps getting Time Limit Exceeds and he is disappointed. Suddenly a bright idea came to his mind!

Here is how his dirty code looks like:

He asks you to write the TOF function in order to optimize the running time of the code with minimizing the number of calls of the dfs function. The input is a directed graph and in the TOF function you have to rearrange the edges of the graph in the list neighbors for each vertex. The number of calls of dfs function depends on the arrangement of neighbors of each vertex.

## Input Format
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 5000) — the number of vertices and then number of directed edges in the input graph.

Each of the next m lines contains a pair of integers ui and vi (1  ≤  ui,  vi  ≤  n), meaning there is a directed $$u_i \rightarrow v_i$$ edge in the input graph.

You may assume that the graph won't contain any self-loops and there is at most one edge between any unordered pair of vertices.

## Output Format
Print a single integer — the minimum possible number of dfs calls that can be achieved with permuting the edges.

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

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Memory is performing a walk on the two-dimensional plane, starting at the origin. He is given a string s with his directions for motion:

- An 'L' indicates he should move one unit left.
- An 'R' indicates he should move one unit right.
- A 'U' indicates he should move one unit up.
- A 'D' indicates he should move one unit down.

But now Memory wants to end at the origin. To do this, he has a special trident. This trident can replace any character in s with any of 'L', 'R', 'U', or 'D'. However, because he doesn't want to wear out the trident, he wants to make the minimum number of edits possible. Please tell Memory what is the minimum number of changes he needs to make to produce a string that, when walked, will end at the origin, or if there is no such string.

## Input Format
The first and only line contains the string s (1 ≤ |s| ≤ 100 000) — the instructions Memory is given.

## Output Format
If there is a string satisfying the conditions, output a single integer — the minimum number of edits required. In case it's not possible to change the sequence in such a way that it will bring Memory to to the origin, output -1.

## Examples
```input
RRU
```
```output
-1
```
-----
```input
UDUR
```
```output
1
```
-----
```input
RUUR
```
```output
2
```

## Note
In the first sample test, Memory is told to walk right, then right, then up. It is easy to see that it is impossible to edit these instructions to form a valid walk.

In the second sample test, Memory is told to walk up, then down, then up, then right. One possible solution is to change s to "LDUR". This string uses 1 edit, which is the minimum possible. It also ends at the origin.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Memory is now interested in the de-evolution of objects, specifically triangles. He starts with an equilateral triangle of side length x, and he wishes to perform operations to obtain an equilateral triangle of side length y.

In a single second, he can modify the length of a single side of the current triangle such that it remains a non-degenerate triangle (triangle of positive area). At any moment of time, the length of each side should be integer.

What is the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y?

## Input Format
The first and only line contains two integers x and y (3 ≤ y < x ≤ 100 000) — the starting and ending equilateral triangle side lengths respectively.

## Output Format
Print a single integer — the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y if he starts with the equilateral triangle of side length x.

## Examples
```input
6 3
```
```output
4
```
-----
```input
8 5
```
```output
3
```
-----
```input
22 4
```
```output
6
```

## Note
In the first sample test, Memory starts with an equilateral triangle of side length 6 and wants one of side length 3. Denote a triangle with sides a, b, and c as (a, b, c). Then, Memory can do $$(6,6,6)\rightarrow(6,6,3)\rightarrow(6,4,3)\rightarrow(3,4,3)\rightarrow(3,3,3)$$.

In the second sample test, Memory can do $$( 8, 8, 8 ) \rightarrow ( 8, 8, 5 ) \rightarrow ( 8, 5, 5 ) \rightarrow ( 5, 5, 5 )$$.

In the third sample test, Memory can do: $$(22,22,22)\rightarrow(7,22,22)\rightarrow(7,22,16)\rightarrow(7,10,16)\rightarrow(7,10,4)$$

$$( 7, 4, 4 ) \rightarrow ( 4, 4, 4 )$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
There are n casinos lined in a row. If Memory plays at casino i, he has probability pi to win and move to the casino on the right (i + 1) or exit the row (if i = n), and a probability 1 - pi to lose and move to the casino on the left (i - 1) or also exit the row (if i = 1).

We say that Memory dominates on the interval i... j if he completes a walk such that,

- He starts on casino i.
- He never looses in casino i.
- He finishes his walk by winning in casino j.

Note that Memory can still walk left of the 1-st casino and right of the casino n and that always finishes the process.

Now Memory has some requests, in one of the following forms:

- 1 i a b: Set $$p_i = \frac{a}{b}$$.
- 2 l r: Print the probability that Memory will dominate on the interval l... r, i.e. compute the probability that Memory will first leave the segment l... r after winning at casino r, if she starts in casino l.

It is guaranteed that at any moment of time p is a non-decreasing sequence, i.e. pi ≤ pi + 1 for all i from 1 to n - 1.

Please help Memory by answering all his requests!

## Input Format
The first line of the input contains two integers n and q(1 ≤ n, q ≤ 100 000),  — number of casinos and number of requests respectively.

The next n lines each contain integers ai and bi (1 ≤ ai < bi ≤ 109)  — $$\frac{a_{i}}{b_{i}}$$ is the probability pi of winning in casino i.

The next q lines each contain queries of one of the types specified above (1 ≤ a < b ≤ 109, 1 ≤ i ≤ n, 1 ≤ l ≤ r ≤ n).

It's guaranteed that there will be at least one query of type 2, i.e. the output will be non-empty. Additionally, it is guaranteed that p forms a non-decreasing sequence at all times.

## Output Format
Print a real number for every request of type 2 — the probability that boy will "dominate" on that interval. Your answer will be considered correct if its absolute error does not exceed 10 - 4.

Namely: let's assume that one of your answers is a, and the corresponding answer of the jury is b. The checker program will consider your answer correct if |a - b| ≤ 10 - 4.

## Examples
```input
3 13
1 3
1 2
2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3
1 2 2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3
```
```output
0.3333333333
0.2000000000
0.1666666667
0.5000000000
0.4000000000
0.6666666667
0.3333333333
0.2500000000
0.2222222222
0.6666666667
0.5714285714
0.6666666667
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are three friend living on the straight line Ox in Lineland. The first friend lives at the point x1, the second friend lives at the point x2, and the third friend lives at the point x3. They plan to celebrate the New Year together, so they need to meet at one point. What is the minimum total distance they have to travel in order to meet at some point and celebrate the New Year?

It's guaranteed that the optimal answer is always integer.

## Input Format
The first line of the input contains three distinct integers x1, x2 and x3 (1 ≤ x1, x2, x3 ≤ 100) — the coordinates of the houses of the first, the second and the third friends respectively.

## Output Format
Print one integer — the minimum total distance the friends need to travel in order to meet together.

## Examples
```input
7 1 4
```
```output
6
```
-----
```input
30 20 10
```
```output
20
```

## Note
In the first sample, friends should meet at the point 4. Thus, the first friend has to travel the distance of 3 (from the point 7 to the point 4), the second friend also has to travel the distance of 3 (from the point 1 to the point 4), while the third friend should not go anywhere because he lives at the point 4.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Modern text editors usually show some information regarding the document being edited. For example, the number of words, the number of pages, or the number of characters.

In this problem you should implement the similar functionality.

You are given a string which only consists of:

- uppercase and lowercase English letters,
- underscore symbols (they are used as separators),
- parentheses (both opening and closing).

It is guaranteed that each opening parenthesis has a succeeding closing parenthesis. Similarly, each closing parentheses has a preceding opening parentheses matching it. For each pair of matching parentheses there are no other parenthesis between them. In other words, each parenthesis in the string belongs to a matching "opening-closing" pair, and such pairs can't be nested.

For example, the following string is valid: "_Hello_Vasya(and_Petya)__bye_(and_OK)".

Word is a maximal sequence of consecutive letters, i.e. such sequence that the first character to the left and the first character to the right of it is an underscore, a parenthesis, or it just does not exist. For example, the string above consists of seven words: "Hello", "Vasya", "and", "Petya", "bye", "and" and "OK". Write a program that finds:

- the length of the longest word outside the parentheses (print 0, if there is no word outside the parentheses),
- the number of words inside the parentheses (print 0, if there is no word inside the parentheses).

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 255) — the length of the given string. The second line contains the string consisting of only lowercase and uppercase English letters, parentheses and underscore symbols.

## Output Format
Print two space-separated integers:

- the length of the longest word outside the parentheses (print 0, if there is no word outside the parentheses),
- the number of words inside the parentheses (print 0, if there is no word inside the parentheses).

## Examples
```input
37
_Hello_Vasya(and_Petya)__bye_(and_OK)
```
```output
5 4
```
-----
```input
37
_a_(_b___c)__de_f(g_)__h__i(j_k_l)m__
```
```output
2 6
```
-----
```input
27
(LoooonG)__shOrt__(LoooonG)
```
```output
5 2
```
-----
```input
5
(___)
```
```output
0 0
```

## Note
In the first sample, the words "Hello", "Vasya" and "bye" are outside any of the parentheses, and the words "and", "Petya", "and" and "OK" are inside. Note, that the word "and" is given twice and you should count it twice in the answer.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp is a music editor at the radio station. He received a playlist for tomorrow, that can be represented as a sequence a1, a2, ..., an, where ai is a band, which performs the i-th song. Polycarp likes bands with the numbers from 1 to m, but he doesn't really like others.

We define as bj the number of songs the group j is going to perform tomorrow. Polycarp wants to change the playlist in such a way that the minimum among the numbers b1, b2, ..., bm will be as large as possible.

Find this maximum possible value of the minimum among the bj (1 ≤ j ≤ m), and the minimum number of changes in the playlist Polycarp needs to make to achieve it. One change in the playlist is a replacement of the performer of the i-th song with any other group.

## Input Format
The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 2000).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the performer of the i-th song.

## Output Format
In the first line print two integers: the maximum possible value of the minimum among the bj (1 ≤ j ≤ m), where bj is the number of songs in the changed playlist performed by the j-th band, and the minimum number of changes in the playlist Polycarp needs to make.

In the second line print the changed playlist.

If there are multiple answers, print any of them.

## Examples
```input
4 2
1 2 3 2
```
```output
2 1
1 2 1 2
```
-----
```input
7 3
1 3 2 2 2 2 1
```
```output
2 1
1 3 3 2 2 2 1
```
-----
```input
4 4
1000000000 100 7 1000000000
```
```output
1 4
1 2 3 4
```

## Note
In the first sample, after Polycarp's changes the first band performs two songs (b1 = 2), and the second band also performs two songs (b2 = 2). Thus, the minimum of these values equals to 2. It is impossible to achieve a higher minimum value by any changes in the playlist.

In the second sample, after Polycarp's changes the first band performs two songs (b1 = 2), the second band performs three songs (b2 = 3), and the third band also performs two songs (b3 = 2). Thus, the best minimum value is 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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Just in case somebody missed it: we have wonderful girls in Arpa’s land.

Arpa has a rooted tree (connected acyclic graph) consisting of n vertices. The vertices are numbered 1 through n, the vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of Dokhtar-kosh things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.

He asks Arpa, for each vertex v, what is the length of the longest simple path in subtree of v that form a Dokhtar-kosh string.

## Input Format
The first line contains integer n (1  ≤  n  ≤  5·105) — the number of vertices in the tree.

(n  -  1) lines follow, the i-th of them contain an integer pi + 1 and a letter ci + 1 (1  ≤  pi + 1  ≤  i, ci + 1 is lowercase English letter, between a and v, inclusively), that mean that there is an edge between nodes pi + 1 and i + 1 and there is a letter ci + 1 written on this edge.

## Output Format
Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.

## Examples
```input
4
1 s
2 a
3 s
```
```output
3 1 1 0
```
-----
```input
5
1 a
2 h
1 a
4 h
```
```output
4 1 0 1 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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
PolandBall is a young, clever Ball. He is interested in prime numbers. He has stated a following hypothesis: "There exists such a positive integer n that for each positive integer m number n·m + 1 is a prime number".

Unfortunately, PolandBall is not experienced yet and doesn't know that his hypothesis is incorrect. Could you prove it wrong? Write a program that finds a counterexample for any n.

## Input Format
The only number in the input is n (1 ≤ n ≤ 1000) — number from the PolandBall's hypothesis.

## Output Format
Output such m that n·m + 1 is not a prime number. Your answer will be considered correct if you output any suitable m such that 1 ≤ m ≤ 103. It is guaranteed the the answer exists.

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

## Note
A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

For the first sample testcase, 3·1 + 1 = 4. We can output 1.

In the second sample testcase, 4·1 + 1 = 5. We cannot output 1 because 5 is prime. However, m = 2 is okay since 4·2 + 1 = 9, which is not a prime number.

Now solve the problem and return the code.