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
Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.

More formally, you are given an odd numer n. Find a set of numbers pi (1 ≤ i ≤ k), such that

1. 1 ≤ k ≤ 3
2. pi is a prime
3. $$\sum_{i=1}^{k} p_i = n$$

The numbers pi do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.

## Input Format
The single line contains an odd number n (3 ≤ n < 109).

## Output Format
In the first line print k (1 ≤ k ≤ 3), showing how many numbers are in the representation you found.

In the second line print numbers pi in any order. If there are multiple possible solutions, you can print any of them.

## Examples
```input
27
```
```output
3
5 11 11
```

## Note
A prime is an integer strictly larger than one that is divisible only by one and by itself.

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
Anton loves transforming one permutation into another one by swapping elements for money, and Ira doesn't like paying for stupid games. Help them obtain the required permutation by paying as little money as possible.

More formally, we have two permutations, p and s of numbers from 1 to n. We can swap pi and pj, by paying |i - j| coins for it. Find and print the smallest number of coins required to obtain permutation s from permutation p. Also print the sequence of swap operations at which we obtain a solution.

## Input Format
The first line contains a single number n (1 ≤ n ≤ 2000) — the length of the permutations.

The second line contains a sequence of n numbers from 1 to n — permutation p. Each number from 1 to n occurs exactly once in this line.

The third line contains a sequence of n numbers from 1 to n — permutation s. Each number from 1 to n occurs once in this line.

## Output Format
In the first line print the minimum number of coins that you need to spend to transform permutation p into permutation s.

In the second line print number k (0 ≤ k ≤ 2·106) — the number of operations needed to get the solution.

In the next k lines print the operations. Each line must contain two numbers i and j (1 ≤ i, j ≤ n, i ≠ j), which means that you need to swap pi and pj.

It is guaranteed that the solution exists.

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

## Note
In the first sample test we swap numbers on positions 3 and 4 and permutation p becomes 4 2 3 1. We pay |3 - 4| = 1 coins for that. On second turn we swap numbers on positions 1 and 3 and get permutation 3241 equal to s. We pay |3 - 1| = 2 coins for that. In total we pay three coins.

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
In this problem you are to calculate the sum of all integers from 1 to n, but you should take all powers of two with minus in the sum.

For example, for n = 4 the sum is equal to  - 1 - 2 + 3 - 4 =  - 4, because 1, 2 and 4 are 20, 21 and 22 respectively.

Calculate the answer for t values of n.

## Input Format
The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of values of n to be processed.

Each of next t lines contains a single integer n (1 ≤ n ≤ 109).

## Output Format
Print the requested sum for each of t integers n given in the input.

## Examples
```input
2
4
1000000000
```
```output
-4
499999998352516354
```

## Note
The answer for the first sample is explained in the statement.

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
You are given the set of vectors on the plane, each of them starting at the origin. Your task is to find a pair of vectors with the minimal non-oriented angle between them.

Non-oriented angle is non-negative value, minimal between clockwise and counterclockwise direction angles. Non-oriented angle is always between 0 and π. For example, opposite directions vectors have angle equals to π.

## Input Format
First line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vectors.

The i-th of the following n lines contains two integers xi and yi (|x|, |y| ≤ 10 000, x2 + y2 > 0) — the coordinates of the i-th vector. Vectors are numbered from 1 to n in order of appearing in the input. It is guaranteed that no two vectors in the input share the same direction (but they still can have opposite directions).

## Output Format
Print two integer numbers a and b (a ≠ b) — a pair of indices of vectors with the minimal non-oriented angle. You can print the numbers in any order. If there are many possible answers, print any.

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

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

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.5 seconds
Memory limit: 256.0 MB

# Problem
You are playing a board card game. In this game the player has two characteristics, x and y — the white magic skill and the black magic skill, respectively. There are n spell cards lying on the table, each of them has four characteristics, ai, bi, ci and di. In one move a player can pick one of the cards and cast the spell written on it, but only if first two of it's characteristics meet the requirement ai ≤ x and bi ≤ y, i.e. if the player has enough magic skill to cast this spell. However, after casting the spell the characteristics of a player change and become equal to x = ci and y = di.

At the beginning of the game both characteristics of a player are equal to zero. The goal of the game is to cast the n-th spell. Your task is to make it in as few moves as possible. You are allowed to use spell in any order and any number of times (for example, you may not use some spells at all).

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of cards on the table.

Each of the next n lines contains four integers ai, bi, ci, di (0 ≤ ai, bi, ci, di ≤ 109) — the characteristics of the corresponding card.

## Output Format
In the first line print a single integer k — the minimum number of moves needed to cast the n-th spell and in the second line print k numbers — the indices of the cards in the order in which you should cast them. In case there are multiple possible solutions, print any of them.

If it is impossible to cast the n-th spell, print  - 1.

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

# Problem
The scientists have recently discovered wormholes — objects in space that allow to travel very long distances between galaxies and star systems.

The scientists know that there are n galaxies within reach. You are in the galaxy number 1 and you need to get to the galaxy number n. To get from galaxy i to galaxy j, you need to fly onto a wormhole (i, j) and in exactly one galaxy day you will find yourself in galaxy j.

Unfortunately, the required wormhole is not always available. Every galaxy day they disappear and appear at random. However, the state of wormholes does not change within one galaxy day. A wormhole from galaxy i to galaxy j exists during each galaxy day taken separately with probability pij. You can always find out what wormholes exist at the given moment. At each moment you can either travel to another galaxy through one of wormholes that exist at this moment or you can simply wait for one galaxy day to see which wormholes will lead from your current position at the next day.

Your task is to find the expected value of time needed to travel from galaxy 1 to galaxy n, if you act in the optimal way. It is guaranteed that this expected value exists.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of galaxies within reach.

Then follows a matrix of n rows and n columns. Each element pij represents the probability that there is a wormhole from galaxy i to galaxy j. All the probabilities are given in percents and are integers. It is guaranteed that all the elements on the main diagonal are equal to 100.

## Output Format
Print a single real value — the expected value of the time needed to travel from galaxy 1 to galaxy n if one acts in an optimal way. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

## Examples
```input
3
100 50 50
0 100 80
0 0 100
```
```output
1.750000000000000
```
-----
```input
2
100 30
40 100
```
```output
3.333333333333333
```

## Note
In the second sample the wormhole from galaxy 1 to galaxy 2 appears every day with probability equal to 0.3. The expected value of days one needs to wait before this event occurs is $$\frac { 1 } { 0. 3 } = 3 \frac { 1 } { 3 }$$.

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

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Today is Wednesday, the third day of the week. What's more interesting is that tomorrow is the last day of the year 2015.

Limak is a little polar bear. He enjoyed this year a lot. Now, he is so eager to the coming year 2016.

Limak wants to prove how responsible a bear he is. He is going to regularly save candies for the entire year 2016! He considers various saving plans. He can save one candy either on some fixed day of the week or on some fixed day of the month.

Limak chose one particular plan. He isn't sure how many candies he will save in the 2016 with his plan. Please, calculate it and tell him.

## Input Format
The only line of the input is in one of the following two formats:

- "x of week" where x (1 ≤ x ≤ 7) denotes the day of the week. The 1-st day is Monday and the 7-th one is Sunday.
- "x of month" where x (1 ≤ x ≤ 31) denotes the day of the month.

## Output Format
Print one integer — the number of candies Limak will save in the year 2016.

## Examples
```input
4 of week
```
```output
52
```
-----
```input
30 of month
```
```output
11
```

## Note
Polar bears use the Gregorian calendar. It is the most common calendar and you likely use it too. You can read about it on Wikipedia if you want to – https://en.wikipedia.org/wiki/Gregorian_calendar. The week starts with Monday.

In the first sample Limak wants to save one candy on each Thursday (the 4-th day of the week). There are 52 Thursdays in the 2016. Thus, he will save 52 candies in total.

In the second sample Limak wants to save one candy on the 30-th day of each month. There is the 30-th day in exactly 11 months in the 2016 — all months but February. It means that Limak will save 11 candies in total.

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
The year 2015 is almost over.

Limak is a little polar bear. He has recently learnt about the binary system. He noticed that the passing year has exactly one zero in its representation in the binary system — 201510 = 111110111112. Note that he doesn't care about the number of zeros in the decimal representation.

Limak chose some interval of years. He is going to count all years from this interval that have exactly one zero in the binary representation. Can you do it faster?

Assume that all positive integers are always written without leading zeros.

## Input Format
The only line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 1018) — the first year and the last year in Limak's interval respectively.

## Output Format
Print one integer – the number of years Limak will count in his chosen interval.

## Examples
```input
5 10
```
```output
2
```
-----
```input
2015 2015
```
```output
1
```
-----
```input
100 105
```
```output
0
```
-----
```input
72057594000000000 72057595000000000
```
```output
26
```

## Note
In the first sample Limak's interval contains numbers 510 = 1012, 610 = 1102, 710 = 1112, 810 = 10002, 910 = 10012 and 1010 = 10102. Two of them (1012 and 1102) have the described property.

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.5 seconds
Memory limit: 512.0 MB

# Problem
Limak is a little polar bear. In the snow he found a scroll with the ancient prophecy. Limak doesn't know any ancient languages and thus is unable to understand the prophecy. But he knows digits!

One fragment of the prophecy is a sequence of n digits. The first digit isn't zero. Limak thinks that it's a list of some special years. It's hard to see any commas or spaces, so maybe ancient people didn't use them. Now Limak wonders what years are listed there.

Limak assumes three things:

- Years are listed in the strictly increasing order;
- Every year is a positive integer number;
- There are no leading zeros.

Limak is going to consider all possible ways to split a sequence into numbers (years), satisfying the conditions above. He will do it without any help. However, he asked you to tell him the number of ways to do so. Since this number may be very large, you are only asked to calculate it modulo 109 + 7.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — the number of digits.

The second line contains a string of digits and has length equal to n. It's guaranteed that the first digit is not '0'.

## Output Format
Print the number of ways to correctly split the given sequence modulo 109 + 7.

## Examples
```input
6
123434
```
```output
8
```
-----
```input
8
20152016
```
```output
4
```

## Note
In the first sample there are 8 ways to split the sequence:

- "123434" = "123434" (maybe the given sequence is just one big number)
- "123434" = "1" + "23434"
- "123434" = "12" + "3434"
- "123434" = "123" + "434"
- "123434" = "1" + "23" + "434"
- "123434" = "1" + "2" + "3434"
- "123434" = "1" + "2" + "3" + "434"
- "123434" = "1" + "2" + "3" + "4" + "34"

Note that we don't count a split "123434" = "12" + "34" + "34" because numbers have to be strictly increasing.

In the second sample there are 4 ways:

- "20152016" = "20152016"
- "20152016" = "20" + "152016"
- "20152016" = "201" + "52016"
- "20152016" = "2015" + "2016"

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

# Problem
Professor GukiZ makes a new robot. The robot are in the point with coordinates (x1, y1) and should go to the point (x2, y2). In a single step the robot can change any of its coordinates (maybe both of them) by one (decrease or increase). So the robot can move in one of the 8 directions. Find the minimal number of steps the robot should make to get the finish position.

## Input Format
The first line contains two integers x1, y1 ( - 109 ≤ x1, y1 ≤ 109) — the start position of the robot.

The second line contains two integers x2, y2 ( - 109 ≤ x2, y2 ≤ 109) — the finish position of the robot.

## Output Format
Print the only integer d — the minimal number of steps to get the finish position.

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

## Note
In the first example robot should increase both of its coordinates by one four times, so it will be in position (4, 4). After that robot should simply increase its y coordinate and get the finish position.

In the second example robot should simultaneously increase x coordinate and decrease y coordinate by one three times.

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
Once Max found an electronic calculator from his grandfather Dovlet's chest. He noticed that the numbers were written with seven-segment indicators (https://en.wikipedia.org/wiki/Seven-segment_display).

Max starts to type all the values from a to b. After typing each number Max resets the calculator. Find the total number of segments printed on the calculator.

For example if a = 1 and b = 3 then at first the calculator will print 2 segments, then — 5 segments and at last it will print 5 segments. So the total number of printed segments is 12.

## Input Format
The only line contains two integers a, b (1 ≤ a ≤ b ≤ 106) — the first and the last number typed by Max.

## Output Format
Print the only integer a — the total number of printed segments.

## Examples
```input
1 3
```
```output
12
```
-----
```input
10 15
```
```output
39
```

Now solve the problem and return the code.