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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
A root tree is a directed acyclic graph that contains one node (root), from which there is exactly one path to any other node.

A root tree is binary if each node has at most two outgoing arcs.

When a binary tree is painted on the plane, all arcs should be directed from top to bottom. That is, each arc going from u to v must meet the condition yu > yv.

You've been given the coordinates of all tree nodes. Your task is to connect these nodes by arcs so as to get the binary root tree and make the total length of the arcs minimum. All arcs of the built tree must be directed from top to bottom.

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 400) — the number of nodes in the tree. Then follow n lines, two integers per line: xi, yi (|xi|, |yi| ≤ 103) — coordinates of the nodes. It is guaranteed that all points are distinct.

## Output Format
If it is impossible to build a binary root tree on the given points, print "-1". Otherwise, print a single real number — the total length of the arcs in the minimum binary tree. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

## Examples
```input
3
0 0
1 0
2 1
```
```output
3.650281539872885
```
-----
```input
4
0 0
1 0
2 1
2 0
```
```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 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: 8.0 seconds
Memory limit: 256.0 MB

# Problem
A ladies' shop has recently opened in the city of Ultima Thule. To get ready for the opening, the shop bought n bags. Each bag is characterised by the total weight ai of the items you can put there. The weird thing is, you cannot use these bags to put a set of items with the total weight strictly less than ai. However the weights of the items that will be sold in the shop haven't yet been defined. That's what you should determine right now.

Your task is to find the set of the items' weights p1, p2, ..., pk (1 ≤ p1 < p2 < ... < pk), such that:

1. Any bag will be used. That is, for any i (1 ≤ i ≤ n) there will be such set of items that their total weight will equal ai. We assume that there is the infinite number of items of any weight. You can put multiple items of the same weight in one bag.
2. For any set of items that have total weight less than or equal to m, there is a bag into which you can put this set. Similarly, a set of items can contain multiple items of the same weight.
3. Of all sets of the items' weights that satisfy points 1 and 2, find the set with the minimum number of weights. In other words, value k should be as small as possible.

Find and print the required set.

## Input Format
The first line contains space-separated integers n and m (1 ≤ n, m ≤ 106). The second line contains n distinct space-separated integers a1, a2, ..., an (1 ≤ a1 < a2 < ... < an ≤ m) — the bags' weight limits.

## Output Format
In the first line print "NO" (without the quotes) if there isn't set pi, that would meet the conditions.

Otherwise, in the first line print "YES" (without the quotes), in the second line print an integer k (showing how many numbers are in the suitable set with the minimum number of weights), in the third line print k space-separated integers p1, p2, ..., pk (1 ≤ p1 < p2 < ... < pk). If there are multiple solutions, print any of them.

## Examples
```input
6 10
5 6 7 8 9 10
```
```output
YES
5
5 6 7 8 9
```
-----
```input
1 10
1
```
```output
NO
```
-----
```input
1 10
6
```
```output
YES
1
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 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
Everybody knows that lucky numbers are positive integers that contain only lucky digits 4 and 7 in their decimal representation. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Polo the Penguin have two positive integers l and r (l < r), both of them are lucky numbers. Moreover, their lengths (that is, the number of digits in the decimal representation without the leading zeroes) are equal to each other.

Let's assume that n is the number of distinct lucky numbers, each of them cannot be greater than r or less than l, and ai is the i-th (in increasing order) number of them. Find a1·a2 + a2·a3 + ... + an - 1·an. As the answer can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

## Input Format
The first line contains a positive integer l, and the second line contains a positive integer r (1 ≤ l < r ≤ 10100000). The numbers are given without any leading zeroes.

It is guaranteed that the lengths of the given numbers are equal to each other and that both of them are lucky numbers.

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

## Examples
```input
4
7
```
```output
28
```
-----
```input
474
777
```
```output
2316330
```

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
A continued fraction of height n is a fraction of form $$a_{1}+\frac{1}{a_{2}+\frac{1}{\cdots+\frac{1}{a_{n}}}}$$. You are given two rational numbers, one is represented as $$\frac{p}{q}$$ and the other one is represented as a finite fraction of height n. Check if they are equal.

## Input Format
The first line contains two space-separated integers p, q (1 ≤ q ≤ p ≤ 1018) — the numerator and the denominator of the first fraction.

The second line contains integer n (1 ≤ n ≤ 90) — the height of the second fraction. The third line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1018) — the continued fraction.

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

## Output Format
Print "YES" if these fractions are equal and "NO" otherwise.

## Examples
```input
9 4
2
2 4
```
```output
YES
```
-----
```input
9 4
3
2 3 1
```
```output
YES
```
-----
```input
9 4
3
1 2 4
```
```output
NO
```

## Note
In the first sample $$2 + \frac{1}{4} = \frac{9}{4}$$.

In the second sample $$2 + \frac{1}{3+\frac{1}{1}} = 2 + \frac{1}{4} = \frac{9}{4}$$.

In the third sample $$1 + \frac{1}{2+\frac{1}{4}} = \frac{13}{9}$$.

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
Olya has got a directed non-weighted graph, consisting of n vertexes and m edges. We will consider that the graph vertexes are indexed from 1 to n in some manner. Then for any graph edge that goes from vertex v to vertex u the following inequation holds: v < u.

Now Olya wonders, how many ways there are to add an arbitrary (possibly zero) number of edges to the graph so as the following conditions were met:

1. You can reach vertexes number i + 1, i + 2, ..., n from any vertex number i (i < n).
2. For any graph edge going from vertex v to vertex u the following inequation fulfills: v < u.
3. There is at most one edge between any two vertexes.
4. The shortest distance between the pair of vertexes i, j (i < j), for which j - i ≤ k holds, equals j - i edges.
5. The shortest distance between the pair of vertexes i, j (i < j), for which j - i > k holds, equals either j - i or j - i - k edges.

We will consider two ways distinct, if there is the pair of vertexes i, j (i < j), such that first resulting graph has an edge from i to j and the second one doesn't have it.

Help Olya. As the required number of ways can be rather large, print it modulo 1000000007 (109 + 7).

## Input Format
The first line contains three space-separated integers n, m, k (2 ≤ n ≤ 106, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106).

The next m lines contain the description of the edges of the initial graph. The i-th line contains a pair of space-separated integers ui, vi (1 ≤ ui < vi ≤ n) — the numbers of vertexes that have a directed edge from ui to vi between them.

It is guaranteed that any pair of vertexes ui, vi has at most one edge between them. It also is guaranteed that the graph edges are given in the order of non-decreasing ui. If there are multiple edges going from vertex ui, then it is guaranteed that these edges are given in the order of increasing vi.

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

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

## Note
In the first sample there are two ways: the first way is not to add anything, the second way is to add a single edge from vertex 2 to vertex 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 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
Ilya is a very clever lion, he lives in an unusual city ZooVille. In this city all the animals have their rights and obligations. Moreover, they even have their own bank accounts. The state of a bank account is an integer. The state of a bank account can be a negative number. This means that the owner of the account owes the bank money.

Ilya the Lion has recently had a birthday, so he got a lot of gifts. One of them (the gift of the main ZooVille bank) is the opportunity to delete the last digit or the digit before last from the state of his bank account no more than once. For example, if the state of Ilya's bank account is -123, then Ilya can delete the last digit and get his account balance equal to -12, also he can remove its digit before last and get the account balance equal to -13. Of course, Ilya is permitted not to use the opportunity to delete a digit from the balance.

Ilya is not very good at math, and that's why he asks you to help him maximize his bank account. Find the maximum state of the bank account that can be obtained using the bank's gift.

## Input Format
The single line contains integer n (10 ≤ |n| ≤ 109) — the state of Ilya's bank account.

## Output Format
In a single line print an integer — the maximum state of the bank account that Ilya can get.

## Examples
```input
2230
```
```output
2230
```
-----
```input
-10
```
```output
0
```
-----
```input
-100003
```
```output
-10000
```

## Note
In the first test sample Ilya doesn't profit from using the present.

In the second test sample you can delete digit 1 and get the state of the account equal to 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
Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s1s2... sn (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers li, ri (1 ≤ li < ri ≤ n). The answer to the query li, ri is the number of such integers i (li ≤ i < ri), that si = si + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

## Input Format
The first line contains string s of length n (2 ≤ n ≤ 105). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers li, ri (1 ≤ li < ri ≤ n).

## Output Format
Print m integers — the answers to the queries in the order in which they are given in the input.

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

# Problem
Ilya is a very good-natured lion. He likes maths. Of all mathematical objects, his favourite one is matrices. Now he's faced a complicated matrix problem he needs to solve.

He's got a square 2n × 2n-sized matrix and 4n integers. You need to arrange all these numbers in the matrix (put each number in a single individual cell) so that the beauty of the resulting matrix with numbers is maximum.

The beauty of a 2n × 2n-sized matrix is an integer, obtained by the following algorithm:

1. Find the maximum element in the matrix. Let's denote it as m.
2. If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2n - 1 × 2n - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices.

As you can see, the algorithm is recursive.

Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.

## Input Format
The first line contains integer 4n (1 ≤ 4n ≤ 2·106). The next line contains 4n integers ai (1 ≤ ai ≤ 109) — the numbers you need to arrange in the 2n × 2n-sized matrix.

## Output Format
On a single line print the maximum value of the beauty of the described matrix.

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

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

## Note
Consider the second sample. You need to arrange the numbers in the matrix as follows:

Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 14.

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
Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as n holes in a row. We will consider the holes numbered from 1 to n, from left to right.

Ilya is really keep on helping his city. So, he wants to fix at least k holes (perharps he can fix more) on a single ZooVille road.

The city has m building companies, the i-th company needs ci money units to fix a road segment containing holes with numbers of at least li and at most ri. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment.

Determine the minimum money Ilya will need to fix at least k holes.

## Input Format
The first line contains three integers n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n). The next m lines contain the companies' description. The i-th line contains three integers li, ri, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ci ≤ 109).

## Output Format
Print a single integer — the minimum money Ilya needs to fix at least k holes.

If it is impossible to fix at least k holes, print -1.

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

## Examples
```input
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6
```
```output
17
```
-----
```input
10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13
```
```output
2
```
-----
```input
10 1 9
5 10 14
```
```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 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
Ilya has recently taken up archaeology. He's recently found two numbers, written in the m-based notation. Each of the found numbers consisted of exactly n digits. Ilya immediately started looking for information about those numbers. He learned that the numbers are part of a cyphered code and the one who can decypher it can get the greatest treasure.

After considerable research Ilya understood that to decypher the code, he should do the following:

- Rearrange digits in the first number in some manner. Similarly, rearrange digits in the second number in some manner. As a result of this operation, the numbers can get leading zeroes.
- Add numbers, digit by digit, modulo m. In other words, we need to get the third number of length n, each digit of the number is the sum of the respective numbers of the found numbers. For example, suppose there are two numbers recorded in the ternary notation, 001210 and 012111, then if you add them to each other digit by digit modulo 3, you will get number 010021.
- The key to the code is the maximum possible number that can be obtained in the previous step.

Help Ilya, find the key to the code.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 105, m > 1). The second line contains the first found number, the third line contains the second found number.

The numbers are recorded as a sequence of digits in the m-based notation. Each digit is an integer from 0 to m - 1. The digits in the line are written in the order from the most significant digits to the least significant ones.

The given numbers can contain leading zeroes.

## Output Format
Print n m-base digits. The resulting third number written in the m-based notation. Print the digits in the order from the most significant digits to the least significant ones.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Fox Ciel and her friends are in a dancing room. There are n boys and m girls here, and they never danced before. There will be some songs, during each song, there must be exactly one boy and one girl are dancing. Besides, there is a special rule:

- either the boy in the dancing pair must dance for the first time (so, he didn't dance with anyone before);
- or the girl in the dancing pair must dance for the first time.

Help Fox Ciel to make a schedule that they can dance as many songs as possible.

## Input Format
The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of boys and girls in the dancing room.

## Output Format
In the first line print k — the number of songs during which they can dance. Then in the following k lines, print the indexes of boys and girls dancing during songs chronologically. You can assume that the boys are indexed from 1 to n, and the girls are indexed from 1 to m.

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

## Note
In test case 1, there are 2 boys and 1 girl. We can have 2 dances: the 1st boy and 1st girl (during the first song), the 2nd boy and 1st girl (during the second song).

And in test case 2, we have 2 boys with 2 girls, the answer is 3.

Now solve the problem and return the code.