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

# Problem
Vasya's bicycle chain drive consists of two parts: n stars are attached to the pedal axle, m stars are attached to the rear wheel axle. The chain helps to rotate the rear wheel by transmitting the pedal rotation.

We know that the i-th star on the pedal axle has ai (0 < a1 < a2 < ... < an) teeth, and the j-th star on the rear wheel axle has bj (0 < b1 < b2 < ... < bm) teeth. Any pair (i, j) (1 ≤ i ≤ n; 1 ≤ j ≤ m) is called a gear and sets the indexes of stars to which the chain is currently attached. Gear (i, j) has a gear ratio, equal to the value $$\frac{b_{j}}{a_{j}}$$.

Since Vasya likes integers, he wants to find such gears (i, j), that their ratios are integers. On the other hand, Vasya likes fast driving, so among all "integer" gears (i, j) he wants to choose a gear with the maximum ratio. Help him to find the number of such gears.

In the problem, fraction $$\frac{b_{j}}{a_{j}}$$ denotes division in real numbers, that is, no rounding is performed.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 50) — the number of stars on the bicycle's pedal axle. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 104) in the order of strict increasing.

The third input line contains integer m (1 ≤ m ≤ 50) — the number of stars on the rear wheel axle. The fourth line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 104) in the order of strict increasing.

It is guaranteed that there exists at least one gear (i, j), that its gear ratio is an integer. The numbers on the lines are separated by spaces.

## Output Format
Print the number of "integer" gears with the maximum ratio among all "integer" gears.

## Examples
```input
2
4 5
3
12 13 15
```
```output
2
```
-----
```input
4
1 2 3 4
5
10 11 12 13 14
```
```output
1
```

## Note
In the first sample the maximum "integer" gear ratio equals 3. There are two gears that have such gear ratio. For one of them a1 = 4, b1 = 12, and for the other a2 = 5, b3 = 15.

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
The World Programming Olympics Medal is a metal disk, consisting of two parts: the first part is a ring with outer radius of r1 cm, inner radius of r2 cm, (0 < r2 < r1) made of metal with density p1 g/cm3. The second part is an inner disk with radius r2 cm, it is made of metal with density p2 g/cm3. The disk is nested inside the ring.

The Olympic jury decided that r1 will take one of possible values of x1, x2, ..., xn. It is up to jury to decide which particular value r1 will take. Similarly, the Olympic jury decided that p1 will take one of possible value of y1, y2, ..., ym, and p2 will take a value from list z1, z2, ..., zk.

According to most ancient traditions the ratio between the outer ring mass mout and the inner disk mass min must equal $$m_{out}/m_{in} = \frac{A}{B}$$, where A, B are constants taken from ancient books. Now, to start making medals, the jury needs to take values for r1, p1, p2 and calculate the suitable value of r2.

The jury wants to choose the value that would maximize radius r2. Help the jury find the sought value of r2. Value r2 doesn't have to be an integer.

Medal has a uniform thickness throughout the area, the thickness of the inner disk is the same as the thickness of the outer ring.

## Input Format
The first input line contains an integer n and a sequence of integers x1, x2, ..., xn. The second input line contains an integer m and a sequence of integers y1, y2, ..., ym. The third input line contains an integer k and a sequence of integers z1, z2, ..., zk. The last line contains two integers A and B.

All numbers given in the input are positive and do not exceed 5000. Each of the three sequences contains distinct numbers. The numbers in the lines are separated by spaces.

## Output Format
Print a single real number — the sought value r2 with absolute or relative error of at most 10 - 6. It is guaranteed that the solution that meets the problem requirements exists.

## Examples
```input
3 1 2 3
1 2
3 3 2 1
1 2
```
```output
2.683281573000
```
-----
```input
4 2 3 6 4
2 1 2
3 10 6 8
2 1
```
```output
2.267786838055
```

## Note
In the first sample the jury should choose the following values: r1 = 3, p1 = 2, p2 = 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
There is a board with a grid consisting of n rows and m columns, the rows are numbered from 1 from top to bottom and the columns are numbered from 1 from left to right. In this grid we will denote the cell that lies on row number i and column number j as (i, j).

A group of six numbers (a, b, c, d, x0, y0), where 0 ≤ a, b, c, d, is a cross, and there is a set of cells that are assigned to it. Cell (x, y) belongs to this set if at least one of two conditions are fulfilled:

- |x0 - x| ≤ a and |y0 - y| ≤ b
- |x0 - x| ≤ c and |y0 - y| ≤ d

The picture shows the cross (0, 1, 1, 0, 2, 3) on the grid 3 × 4.

Your task is to find the number of different groups of six numbers, (a, b, c, d, x0, y0) that determine the crosses of an area equal to s, which are placed entirely on the grid. The cross is placed entirely on the grid, if any of its cells is in the range of the grid (that is for each cell (x, y) of the cross 1 ≤ x ≤ n; 1 ≤ y ≤ m holds). The area of the cross is the number of cells it has.

Note that two crosses are considered distinct if the ordered groups of six numbers that denote them are distinct, even if these crosses coincide as sets of points.

## Input Format
The input consists of a single line containing three integers n, m and s (1 ≤ n, m ≤ 500, 1 ≤ s ≤ n·m). The integers are separated by a space.

## Output Format
Print a single integer — the number of distinct groups of six integers that denote crosses with area s and that are fully placed on the n × m grid.

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
2 2 1
```
```output
4
```
-----
```input
3 4 5
```
```output
4
```

## Note
In the first sample the sought groups of six numbers are: (0, 0, 0, 0, 1, 1), (0, 0, 0, 0, 1, 2), (0, 0, 0, 0, 2, 1), (0, 0, 0, 0, 2, 2).

In the second sample the sought groups of six numbers are: (0, 1, 1, 0, 2, 2), (0, 1, 1, 0, 2, 3), (1, 0, 0, 1, 2, 2), (1, 0, 0, 1, 2, 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 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 non-empty string s is called binary, if it consists only of characters "0" and "1". Let's number the characters of binary string s from 1 to the string's length and let's denote the i-th character in string s as si.

Binary string s with length n is periodical, if there is an integer 1 ≤ k < n such that:

- k is a divisor of number n
- for all 1 ≤ i ≤ n - k, the following condition fulfills: si = si + k

For example, binary strings "101010" and "11" are periodical and "10" and "10010" are not.

A positive integer x is periodical, if its binary representation (without leading zeroes) is a periodic string.

Your task is to calculate, how many periodic numbers are in the interval from l to r (both ends are included).

## Input Format
The single input line contains two integers l and r (1 ≤ l ≤ r ≤ 1018). The numbers are separated by a space.

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 a single integer, showing how many periodic numbers are in the interval from l to r (both ends are included).

## Examples
```input
1 10
```
```output
3
```
-----
```input
25 38
```
```output
2
```

## Note
In the first sample periodic numbers are 3, 7 and 10.

In the second sample periodic numbers are 31 and 36.

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
Little boy Valera studies an algorithm of sorting an integer array. After studying the theory, he went on to the practical tasks. As a result, he wrote a program that sorts an array of n integers a1, a2, ..., an in the non-decreasing order. The pseudocode of the program, written by Valera, is given below. The input of the program gets number n and array a.

But Valera could have made a mistake, because he hasn't yet fully learned the sorting algorithm. If Valera made a mistake in his program, you need to give a counter-example that makes his program work improperly (that is, the example that makes the program sort the array not in the non-decreasing order). If such example for the given value of n doesn't exist, print -1.

## Input Format
You've got a single integer n (1 ≤ n ≤ 50) — the size of the sorted array.

## Output Format
Print n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the counter-example, for which Valera's algorithm won't work correctly. If the counter-example that meets the described conditions is impossible to give, print -1.

If there are several counter-examples, consisting of n numbers, you are allowed to print any of them.

## Examples
```input
1
```
```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
General Payne has a battalion of n soldiers. The soldiers' beauty contest is coming up, it will last for k days. Payne decided that his battalion will participate in the pageant. Now he has choose the participants.

All soldiers in the battalion have different beauty that is represented by a positive integer. The value ai represents the beauty of the i-th soldier.

On each of k days Generals has to send a detachment of soldiers to the pageant. The beauty of the detachment is the sum of the beauties of the soldiers, who are part of this detachment. Payne wants to surprise the jury of the beauty pageant, so each of k days the beauty of the sent detachment should be unique. In other words, all k beauties of the sent detachments must be distinct numbers.

Help Payne choose k detachments of different beauties for the pageant. Please note that Payne cannot just forget to send soldiers on one day, that is, the detachment of soldiers he sends to the pageant should never be empty.

## Input Format
The first line contains two integers n, k (1 ≤ n ≤ 50; 1 ≤ k ≤  $$\frac{n(n+1)}{2}$$) — the number of soldiers and the number of days in the pageant, correspondingly. The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 107) — the beauties of the battalion soldiers.

It is guaranteed that Payne's battalion doesn't have two soldiers with the same beauty.

## Output Format
Print k lines: in the i-th line print the description of the detachment that will participate in the pageant on the i-th day. The description consists of integer ci (1 ≤ ci ≤ n) — the number of soldiers in the detachment on the i-th day of the pageant and ci distinct integers p1, i, p2, i, ..., pci, i — the beauties of the soldiers in the detachment on the i-th day of the pageant. The beauties of the soldiers are allowed to print in any order.

Separate numbers on the lines by spaces. It is guaranteed that there is the solution that meets the problem conditions. If there are multiple solutions, print any of them.

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

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
You've got an undirected graph, consisting of n vertices and m edges. We will consider the graph's vertices numbered with integers from 1 to n. Each vertex of the graph has a color. The color of the i-th vertex is an integer ci.

Let's consider all vertices of the graph, that are painted some color k. Let's denote a set of such as V(k). Let's denote the value of the neighbouring color diversity for color k as the cardinality of the set Q(k) = {cu :  cu ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.

Your task is to find such color k, which makes the cardinality of set Q(k) maximum. In other words, you want to find the color that has the most diverse neighbours. Please note, that you want to find such color k, that the graph has at least one vertex with such color.

## Input Format
The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) — the number of vertices end edges of the graph, correspondingly. The second line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105) — the colors of the graph vertices. The numbers on the line are separated by spaces.

Next m lines contain the description of the edges: the i-th line contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the numbers of the vertices, connected by the i-th edge.

It is guaranteed that the given graph has no self-loops or multiple edges.

## Output Format
Print the number of the color which has the set of neighbours with the maximum cardinality. It there are multiple optimal colors, print the color with the minimum number. Please note, that you want to find such color, that the graph has at least one vertex with such color.

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

# Problem
Bob is preparing to pass IQ test. The most frequent task in this test is to find out which one of the given n numbers differs from the others. Bob observed that one number usually differs from the others in evenness. Help Bob — to check his answers, he needs a program that among the given n numbers finds one that is different in evenness.

## Input Format
The first line contains integer n (3 ≤ n ≤ 100) — amount of numbers in the task. The second line contains n space-separated natural numbers, not exceeding 100. It is guaranteed, that exactly one of these numbers differs from the others in evenness.

## Output Format
Output index of number that differs from the others in evenness. Numbers are numbered from 1 in the input order.

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

# Problem
Phone number in Berland is a sequence of n digits. Often, to make it easier to memorize the number, it is divided into groups of two or three digits. For example, the phone number 1198733 is easier to remember as 11-987-33. Your task is to find for a given phone number any of its divisions into groups of two or three digits.

## Input Format
The first line contains integer n (2 ≤ n ≤ 100) — amount of digits in the phone number. The second line contains n digits — the phone number to divide into groups.

## Output Format
Output any of divisions of the given phone number into groups of two or three digits. Separate groups by single character -. If the answer is not unique, output any.

## Examples
```input
6
549871
```
```output
54-98-71
```
-----
```input
7
1198733
```
```output
11-987-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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Berland Government decided to improve relations with neighboring countries. First of all, it was decided to build new roads so that from each city of Berland and neighboring countries it became possible to reach all the others. There are n cities in Berland and neighboring countries in total and exactly n - 1 two-way roads. Because of the recent financial crisis, the Berland Government is strongly pressed for money, so to build a new road it has to close some of the existing ones. Every day it is possible to close one existing road and immediately build a new one. Your task is to determine how many days would be needed to rebuild roads so that from each city it became possible to reach all the others, and to draw a plan of closure of old roads and building of new ones.

## Input Format
The first line contains integer n (2 ≤ n ≤ 1000) — amount of cities in Berland and neighboring countries. Next n - 1 lines contain the description of roads. Each road is described by two space-separated integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — pair of cities, which the road connects. It can't be more than one road between a pair of cities. No road connects the city with itself.

## Output Format
Output the answer, number t — what is the least amount of days needed to rebuild roads so that from each city it became possible to reach all the others. Then output t lines — the plan of closure of old roads and building of new ones. Each line should describe one day in the format i j u v — it means that road between cities i and j became closed and a new road between cities u and v is built. Cities are numbered from 1. If the answer is not unique, output any.

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

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: 256.0 MB

# Problem
Maxim has got a calculator. The calculator has two integer cells. Initially, the first cell contains number 1, and the second cell contains number 0. In one move you can perform one of the following operations:

1. Let's assume that at the current time the first cell contains number a, and the second cell contains number b. Write to the second cell number b + 1;
2. Let's assume that at the current time the first cell contains number a, and the second cell contains number b. Write to the first cell number a·b.

Maxim is wondering, how many integers x (l ≤ x ≤ r) are there, such that we can write the number x to the first cell of the calculator, having performed at most p moves.

## Input Format
The first line contains three integers: l, r, p (2 ≤ l ≤ r ≤ 109, 1 ≤ p ≤ 100).

The numbers in the line are separated by single spaces.

## Output Format
In a single line print a single integer — the answer to the problem.

## Examples
```input
2 10 3
```
```output
1
```
-----
```input
2 111 100
```
```output
106
```
-----
```input
2 111 11
```
```output
47
```

Now solve the problem and return the code.