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
Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.

Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k.

## Input Format
The only line of the input contains a single integer n (2 ≤ n ≤ 100 000).

## Output Format
The first line of the output contains a single integer k — maximum possible number of primes in representation.

The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.

## Examples
```input
5
```
```output
2
2 3
```
-----
```input
6
```
```output
3
2 2 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 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
Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal.

Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points.

## Input Format
The input consists of three lines, each containing a pair of integer coordinates xi and yi ( - 1000 ≤ xi, yi ≤ 1000). It's guaranteed that these three points do not lie on the same line and no two of them coincide.

## Output Format
First print integer k — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices.

Then print k lines, each containing a pair of integer — possible coordinates of the fourth point.

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

## Note
If you need clarification of what parallelogram is, please check Wikipedia page:

https://en.wikipedia.org/wiki/Parallelogram

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation of integers from 1 to n. Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally:

1. Pick a random segment (continuous subsequence) from l to r. All $$\frac{n(n+1)}{2}$$ segments are equiprobable.
2. Let k = r - l + 1, i.e. the length of the chosen segment. Pick a random permutation of integers from 1 to k, p1, p2, ..., pk. All k! permutation are equiprobable.
3. This permutation is applied to elements of the chosen segment, i.e. permutation a1, a2, ..., al - 1, al, al + 1, ..., ar - 1, ar, ar + 1, ..., an is transformed to a1, a2, ..., al - 1, al - 1 + p1, al - 1 + p2, ..., al - 1 + pk - 1, al - 1 + pk, ar + 1, ..., an.

Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs (i, j) such that i < j and ai > aj. Find the expected number of inversions after we apply exactly one operation mentioned above.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.

## Output Format
Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 9.

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 | } { \operatorname* { m a x } ( 1, b ) } } \leq 1 0 ^ { - 9 }$$.

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

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
Our beloved detective, Sherlock is currently trying to catch a serial killer who kills a person each day. Using his powers of deduction, he came to know that the killer has a strategy for selecting his next victim.

The killer starts with two potential victims on his first day, selects one of these two, kills selected victim and replaces him with a new person. He repeats this procedure each day. This way, each day he has two potential victims to choose from. Sherlock knows the initial two potential victims. Also, he knows the murder that happened on a particular day and the new person who replaced this victim.

You need to help him get all the pairs of potential victims at each day so that Sherlock can observe some pattern.

## Input Format
First line of input contains two names (length of each of them doesn't exceed 10), the two initials potential victims. Next line contains integer n (1 ≤ n ≤ 1000), the number of days.

Next n lines contains two names (length of each of them doesn't exceed 10), first being the person murdered on this day and the second being the one who replaced that person.

The input format is consistent, that is, a person murdered is guaranteed to be from the two potential victims at that time. Also, all the names are guaranteed to be distinct and consists of lowercase English letters.

## Output Format
Output n + 1 lines, the i-th line should contain the two persons from which the killer selects for the i-th murder. The (n + 1)-th line should contain the two persons from which the next victim is selected. In each line, the two names can be printed in any order.

## Examples
```input
ross rachel
4
ross joey
rachel phoebe
phoebe monica
monica chandler
```
```output
ross rachel
joey rachel
joey phoebe
joey monica
joey chandler
```
-----
```input
icm codeforces
1
codeforces technex
```
```output
icm codeforces
icm technex
```

## Note
In first example, the killer starts with ross and rachel.

- After day 1, ross is killed and joey appears.
- After day 2, rachel is killed and phoebe appears.
- After day 3, phoebe is killed and monica appears.
- After day 4, monica is killed and chandler appears.

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
Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry.

He bought n pieces of jewelry. The i-th piece has price equal to i + 1, that is, the prices of the jewelry are 2, 3, 4, ... n + 1.

Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.

Help Sherlock complete this trivial task.

## Input Format
The only line contains single integer n (1 ≤ n ≤ 100000) — the number of jewelry pieces.

## Output Format
The first line of output should contain a single integer k, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints.

The next line should consist of n space-separated integers (between 1 and k) that specify the color of each piece in the order of increasing price.

If there are multiple ways to color the pieces using k colors, you can output any of them.

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

## Note
In the first input, the colors for first, second and third pieces of jewelry having respective prices 2, 3 and 4 are 1, 1 and 2 respectively.

In this case, as 2 is a prime divisor of 4, colors of jewelry having prices 2 and 4 must be distinct.

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
Molly Hooper has n different kinds of chemicals arranged in a line. Each of the chemicals has an affection value, The i-th of them has affection value ai.

Molly wants Sherlock to fall in love with her. She intends to do this by mixing a contiguous segment of chemicals together to make a love potion with total affection value as a non-negative integer power of k. Total affection value of a continuous segment of chemicals is the sum of affection values of each chemical in that segment.

Help her to do so in finding the total number of such segments.

## Input Format
The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection value is a non-negative power of this number k. (1 ≤ n ≤ 105, 1 ≤ |k| ≤ 10).

Next line contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — affection values of chemicals.

## Output Format
Output a single integer — the number of valid segments.

## Examples
```input
4 2
2 2 2 2
```
```output
8
```
-----
```input
4 -3
3 -6 -3 12
```
```output
3
```

## Note
Do keep in mind that k0 = 1.

In the first sample, Molly can get following different affection values:

- 2: segments [1, 1], [2, 2], [3, 3], [4, 4];
- 4: segments [1, 2], [2, 3], [3, 4];
- 6: segments [1, 3], [2, 4];
- 8: segments [1, 4].

Out of these, 2, 4 and 8 are powers of k = 2. Therefore, the answer is 8.

In the second sample, Molly can choose segments [1, 2], [3, 3], [3, 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 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
Moriarty has trapped n people in n distinct rooms in a hotel. Some rooms are locked, others are unlocked. But, there is a condition that the people in the hotel can only escape when all the doors are unlocked at the same time. There are m switches. Each switch control doors of some rooms, but each door is controlled by exactly two switches.

You are given the initial configuration of the doors. Toggling any switch, that is, turning it ON when it is OFF, or turning it OFF when it is ON, toggles the condition of the doors that this switch controls. Say, we toggled switch 1, which was connected to room 1, 2 and 3 which were respectively locked, unlocked and unlocked. Then, after toggling the switch, they become unlocked, locked and locked.

You need to tell Sherlock, if there exists a way to unlock all doors at the same time.

## Input Format
First line of input contains two integers n and m (2 ≤ n ≤ 105, 2 ≤ m ≤ 105) — the number of rooms and the number of switches.

Next line contains n space-separated integers r1, r2, ..., rn (0 ≤ ri ≤ 1) which tell the status of room doors. The i-th room is locked if ri = 0, otherwise it is unlocked.

The i-th of next m lines contains an integer xi (0 ≤ xi ≤ n) followed by xi distinct integers separated by space, denoting the number of rooms controlled by the i-th switch followed by the room numbers that this switch controls. It is guaranteed that the room numbers are in the range from 1 to n. It is guaranteed that each door is controlled by exactly two switches.

## Output Format
Output "YES" without quotes, if it is possible to open all doors at the same time, otherwise output "NO" without quotes.

## Examples
```input
3 3
1 0 1
2 1 3
2 1 2
2 2 3
```
```output
NO
```
-----
```input
3 3
1 0 1
3 1 2 3
1 2
2 1 3
```
```output
YES
```
-----
```input
3 3
1 0 1
3 1 2 3
2 1 2
1 3
```
```output
NO
```

## Note
In the second example input, the initial statuses of the doors are [1, 0, 1] (0 means locked, 1 — unlocked).

After toggling switch 3, we get [0, 0, 0] that means all doors are locked.

Then, after toggling switch 1, we get [1, 1, 1] that means all doors are unlocked.

It can be seen that for the first and for the third example inputs it is not possible to make all doors unlocked.

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 Holmes children are fighting over who amongst them is the cleverest.

Mycroft asked Sherlock and Eurus to find value of f(n), where f(1) = 1 and for n ≥ 2, f(n) is the number of distinct ordered positive integer pairs (x, y) that satisfy x + y = n and gcd(x, y) = 1. The integer gcd(a, b) is the greatest common divisor of a and b.

Sherlock said that solving this was child's play and asked Mycroft to instead get the value of $$g(n) = \sum_{d|n} f\left(\frac{n}{d}\right)$$. Summation is done over all positive integers d that divide n.

Eurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft.

She defined a k-composite function Fk(n) recursively as follows:

$$$$

She wants them to tell the value of Fk(n) modulo 1000000007.

## Input Format
A single line of input contains two space separated integers n (1 ≤ n ≤ 1012) and k (1 ≤ k ≤ 1012) indicating that Eurus asks Sherlock and Mycroft to find the value of Fk(n) modulo 1000000007.

## Output Format
Output a single integer — the value of Fk(n) modulo 1000000007.

## Examples
```input
7 1
```
```output
6
```
-----
```input
10 2
```
```output
4
```

## Note
In the first case, there are 6 distinct ordered pairs (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) satisfying x + y = 7 and gcd(x, y) = 1. Hence, f(7) = 6. So, F1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 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 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: 512.0 MB

# Problem
Sherlock met Moriarty for a final battle of wits. He gave him a regular n sided convex polygon. In addition to it, he gave him certain diagonals to form regions on the polygon. It was guaranteed that the diagonals did not intersect in interior points.

He took each of the region and calculated its importance value. Importance value for a region formed by vertices a1, a2, ... , ax of the polygon will be given by 2a1 + 2a2 + ... + 2ax. Then, he sorted these regions on the basis of their importance value in ascending order. After that he assigned each region an index from 1 to k, where k is the number of regions, and index of region is its position in the sorted array calculated above.

He wants Moriarty to color the regions using not more than 20 colors, such that two regions have same color only if all the simple paths between these two regions have at least one region with color value less than the color value assigned to these regions. Simple path between two regions f and h is a sequence of regions r1, r2, ... rt such that r1 = f, rt = h, for each 1 ≤ i < t regions ri and ri + 1 share an edge, and ri = rj if and only if i = j.

Moriarty couldn't answer and asks Sherlock to solve it himself. Help Sherlock in doing so.

## Input Format
First line contains two integers n and m (3 ≤ n ≤ 100000, 0 ≤ m ≤ n - 3), the number of vertices in the polygon and the number of diagonals added.

Each of the next m lines contains two integers a and b (1 ≤ a, b ≤ n), describing a diagonal between vertices a and b. It is guaranteed that the diagonals are correct, i. e. a and b don't coincide and are not neighboring. It is guaranteed that the diagonals do not intersect.

## Output Format
Let the number of regions be k.

Output k space-separated integers, each between 1 and 20, representing the colors of the regions in the order of increasing importance.

If there are multiple answers, print any of them. It can be shown that at least one answer exists.

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

## Note
In 2nd input, regions formed in order after sorting will be (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), i.e, region (1, 2, 3) is first region followed by region (1, 3, 4) and so on.

So, we can color regions 1 and 3 with same color, as region number 2 is on the path from 1 to 3 and it has color 1 which is less than color of 1 and 3, i.e., color number 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 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: 512.0 MB

# Problem
Boris really likes numbers and even owns a small shop selling interesting numbers. He has n decimal numbers Bi. Cost of the number in his shop is equal to the sum of costs of its digits. You are given the values cd, where cd is the cost of the digit d. Of course, Boris is interested in that numbers he owns have the maximum cost possible.

Recently Boris got hold of the magical artifact A, which can allow him to increase the cost of his collection. Artifact is a string, consisting of digits and '?' symbols. To use the artifact, Boris must replace all '?' with digits to get a decimal number without leading zeros (it is also not allowed to get number 0). After that, the resulting number is added to all numbers Bi in Boris' collection. He uses the artifact exactly once.

What is the maximum cost of the collection Boris can achieve after using the artifact?

## Input Format
First line contains artifact A, consisting of digits '0'–'9' and '?' symbols (1 ≤ |A| ≤ 1000). Next line contains n — the amount of numbers in Boris' collection (1 ≤ n ≤ 1000). Next n lines contain integers Bi (1 ≤ Bi < 101000). A doesn't start with '0'.

Last line contains ten integers — costs of digits c0, c1, ..., c9 (0 ≤ ci ≤ 1000).

## Output Format
Output one integer — the maximum possible cost of the collection after using the artifact.

## Examples
```input
42
3
89
1
958
0 0 1 1 2 2 3 3 4 4
```
```output
4
```
-----
```input
?5?
4
2203
5229
276
6243
2 1 6 1 1 2 5 2 2 3
```
```output
62
```

## Note
In the second sample input, the optimal way is to compose the number 453. After adding this number, Boris will have numbers 2656, 5682, 729 and 6696. The total cost of all digits in them is equal to 18 + 15 + 11 + 18 = 62.

Now solve the problem and return the code.