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
Today Patrick waits for a visit from his friend Spongebob. To prepare for the visit, Patrick needs to buy some goodies in two stores located near his house. There is a d1 meter long road between his house and the first shop and a d2 meter long road between his house and the second shop. Also, there is a road of length d3 directly connecting these two shops to each other. Help Patrick calculate the minimum distance that he needs to walk in order to go to both shops and return to his house.

Patrick always starts at his house. He should visit both shops moving only along the three existing roads and return back to his house. He doesn't mind visiting the same shop or passing the same road multiple times. The only goal is to minimize the total distance traveled.

## Input Format
The first line of the input contains three integers d1, d2, d3 (1 ≤ d1, d2, d3 ≤ 108) — the lengths of the paths.

- d1 is the length of the path connecting Patrick's house and the first shop;
- d2 is the length of the path connecting Patrick's house and the second shop;
- d3 is the length of the path connecting both shops.

## Output Format
Print the minimum distance that Patrick will have to walk in order to visit both shops and return to his house.

## Examples
```input
10 20 30
```
```output
60
```
-----
```input
1 1 5
```
```output
4
```

## Note
The first sample is shown on the picture in the problem statement. One of the optimal routes is: house $$\rightarrow$$ first shop $$\rightarrow$$ second shop $$\rightarrow$$ house.

In the second sample one of the optimal routes is: house $$\rightarrow$$ first shop $$\rightarrow$$ house $$\rightarrow$$ second shop $$\rightarrow$$ house.

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
While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick's personal stuff and found a sequence a1, a2, ..., am of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence f1, f2, ..., fn of length n and for each number ai got number bi = fai. To finish the prank he erased the initial sequence ai.

It's hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.

## Input Format
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the lengths of sequences fi and bi respectively.

The second line contains n integers, determining sequence f1, f2, ..., fn (1 ≤ fi ≤ n).

The last line contains m integers, determining sequence b1, b2, ..., bm (1 ≤ bi ≤ n).

## Output Format
Print "Possible" if there is exactly one sequence ai, such that bi = fai for all i from 1 to m. Then print m integers a1, a2, ..., am.

If there are multiple suitable sequences ai, print "Ambiguity".

If Spongebob has made a mistake in his calculations and no suitable sequence ai exists, print "Impossible".

## Examples
```input
3 3
3 2 1
1 2 3
```
```output
Possible
3 2 1
```
-----
```input
3 3
1 1 1
1 1 1
```
```output
Ambiguity
```
-----
```input
3 3
1 2 1
3 3 3
```
```output
Impossible
```

## Note
In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.

In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.

In the third sample fi ≠ 3 for all i, so no sequence ai transforms into such bi and we can say for sure that Spongebob has made a mistake.

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
One day Squidward, Spongebob and Patrick decided to go to the beach. Unfortunately, the weather was bad, so the friends were unable to ride waves. However, they decided to spent their time building sand castles.

At the end of the day there were n castles built by friends. Castles are numbered from 1 to n, and the height of the i-th castle is equal to hi. When friends were about to leave, Squidward noticed, that castles are not ordered by their height, and this looks ugly. Now friends are going to reorder the castles in a way to obtain that condition hi ≤ hi + 1 holds for all i from 1 to n - 1.

Squidward suggested the following process of sorting castles:

- Castles are split into blocks — groups of consecutive castles. Therefore the block from i to j will include castles i, i + 1, ..., j. A block may consist of a single castle.
- The partitioning is chosen in such a way that every castle is a part of exactly one block.
- Each block is sorted independently from other blocks, that is the sequence hi, hi + 1, ..., hj becomes sorted.
- The partitioning should satisfy the condition that after each block is sorted, the sequence hi becomes sorted too. This may always be achieved by saying that the whole sequence is a single block.

Even Patrick understands that increasing the number of blocks in partitioning will ease the sorting process. Now friends ask you to count the maximum possible number of blocks in a partitioning that satisfies all the above requirements.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of castles Spongebob, Patrick and Squidward made from sand during the day.

The next line contains n integers hi (1 ≤ hi ≤ 109). The i-th of these integers corresponds to the height of the i-th castle.

## Output Format
Print the maximum possible number of blocks in a valid partitioning.

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

## Note
In the first sample the partitioning looks like that: [1][2][3].

In the second sample the partitioning is: [2, 1][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 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
Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.

## Input Format
The first line of the input contains a single integer x (1 ≤ x ≤ 1018) — the number of squares inside the tables Spongebob is interested in.

## Output Format
First print a single integer k — the number of tables with exactly x distinct squares inside.

Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.

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

## Note
In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.

In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Rooted tree is a connected graph without any simple cycles with one vertex selected as a root. In this problem the vertex number 1 will always serve as a root.

Lowest common ancestor of two vertices u and v is the farthest from the root vertex that lies on both the path from u to the root and on path from v to the root. We will denote it as LCA(u, v).

Sandy had a rooted tree consisting of n vertices that she used to store her nuts. Unfortunately, the underwater storm broke her tree and she doesn't remember all it's edges. She only managed to restore m edges of the initial tree and q triples ai, bi and ci, for which she supposes LCA(ai, bi) = ci.

Help Sandy count the number of trees of size n with vertex 1 as a root, that match all the information she remembered. If she made a mess and there are no such trees then print 0. Two rooted trees are considered to be distinct if there exists an edge that occur in one of them and doesn't occur in the other one.

## Input Format
The first line of the input contains three integers n, m and q (1 ≤ n ≤ 13, 0 ≤ m < n, 0 ≤ q ≤ 100) — the number of vertices, the number of edges and LCA triples remembered by Sandy respectively.

Each of the next m lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the numbers of vertices connected by the i-th edge. It's guaranteed that this set of edges is a subset of edges of some tree.

The last q lines contain the triplets of numbers ai, bi, ci (1 ≤ ai, bi, ci ≤ n). Each of these triples define LCA(ai, bi) = ci. It's not guaranteed that there exists a tree that satisfy all the given LCA conditions.

## Output Format
Print a single integer — the number of trees of size n that satisfy all the conditions.

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

## Note
In the second sample correct answer looks like this:

In the third sample there are two possible trees:

In the fourth sample the answer is 0 because the information about LCA is inconsistent.

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 string s. Let's call word any largest sequence of consecutive symbols without symbols ',' (comma) and ';' (semicolon). For example, there are four words in string "aba,123;1a;0": "aba", "123", "1a", "0". A word can be empty: for example, the string s=";;" contains three empty words separated by ';'.

You should find all words in the given string that are nonnegative INTEGER numbers without leading zeroes and build by them new string a. String a should contain all words that are numbers separating them by ',' (the order of numbers should remain the same as in the string s). By all other words you should build string b in the same way (the order of numbers should remain the same as in the string s).

Here strings "101", "0" are INTEGER numbers, but "01" and "1.0" are not.

For example, for the string aba,123;1a;0 the string a would be equal to "123,0" and string b would be equal to "aba,1a".

## Input Format
The only line of input contains the string s (1 ≤ |s| ≤ 105). The string contains only symbols '.' (ASCII 46), ',' (ASCII 44), ';' (ASCII 59), digits, lowercase and uppercase latin letters.

## Output Format
Print the string a to the first line and string b to the second line. Each string should be surrounded by quotes (ASCII 34).

If there are no words that are numbers print dash (ASCII 45) on the first line. If all words are numbers print dash on the second line.

## Examples
```input
aba,123;1a;0
```
```output
"123,0"
"aba,1a"
```
-----
```input
1;;01,a0,
```
```output
"1"
",01,a0,"
```
-----
```input
1
```
```output
"1"
-
```
-----
```input
a
```
```output
-
"a"
```

## Note
In the second example the string s contains five words: "1", "", "01", "a0", "".

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 two arrays of integers a and b. For each element of the second array bj you should find the number of elements in array a that are less than or equal to the value bj.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the sizes of arrays a and b.

The second line contains n integers — the elements of array a ( - 109 ≤ ai ≤ 109).

The third line contains m integers — the elements of array b ( - 109 ≤ bj ≤ 109).

## Output Format
Print m integers, separated by spaces: the j-th of which is equal to the number of such elements in array a that are less than or equal to the value bj.

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

# Problem
A string is called palindrome if it reads the same from left to right and from right to left. For example "kazak", "oo", "r" and "mikhailrubinchikkihcniburliahkim" are palindroms, but strings "abb" and "ij" are not.

You are given string s consisting of lowercase Latin letters. At once you can choose any position in the string and change letter in that position to any other lowercase letter. So after each changing the length of the string doesn't change. At first you can change some letters in s. Then you can permute the order of letters as you want. Permutation doesn't count as changes.

You should obtain palindrome with the minimal number of changes. If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. So firstly you should minimize the number of changes and then minimize the palindrome lexicographically.

## Input Format
The only line contains string s (1 ≤ |s| ≤ 2·105) consisting of only lowercase Latin letters.

## Output Format
Print the lexicographically smallest palindrome that can be obtained with the minimal number of changes.

## Examples
```input
aabc
```
```output
abba
```
-----
```input
aabcd
```
```output
abcba
```

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 two circles. Find the area of their intersection.

## Input Format
The first line contains three integers x1, y1, r1 ( - 109 ≤ x1, y1 ≤ 109, 1 ≤ r1 ≤ 109) — the position of the center and the radius of the first circle.

The second line contains three integers x2, y2, r2 ( - 109 ≤ x2, y2 ≤ 109, 1 ≤ r2 ≤ 109) — the position of the center and the radius of the second circle.

## Output Format
Print the area of the intersection of the circles. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

## Examples
```input
0 0 4
6 0 4
```
```output
7.25298806364175601379
```
-----
```input
0 0 5
11 0 5
```
```output
0.00000000000000000000
```

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 an undirected bipartite graph without multiple edges. You should paint the edges of graph to minimal number of colours, so that no two adjacent edges have the same colour.

## Input Format
The first line contains three integers a, b, m (1 ≤ a, b ≤ 1000, 0 ≤ m ≤ 105), a is the size of the first part, b is the size of the second part, m is the number of edges in the graph.

Each of the next m lines contains two integers x, y (1 ≤ x ≤ a, 1 ≤ y ≤ b), where x is the number of the vertex in the first part and y is the number of the vertex in the second part. It is guaranteed that there are no multiple edges.

## Output Format
In the first line print integer c — the minimal number of colours. The second line should contain m integers from 1 to c — the colours of the edges (in the order they appear in the input).

If there are several solutions, you can print any one of them.

## Examples
```input
4 3 5
1 2
2 2
3 2
4 1
4 3
```
```output
3
1 2 3 1 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
Kevin Sun has just finished competing in Codeforces Round #334! The round was 120 minutes long and featured five problems with maximum point values of 500, 1000, 1500, 2000, and 2500, respectively. Despite the challenging tasks, Kevin was uncowed and bulldozed through all of them, distinguishing himself from the herd as the best cowmputer scientist in all of Bovinia. Kevin knows his submission time for each problem, the number of wrong submissions that he made on each problem, and his total numbers of successful and unsuccessful hacks. Because Codeforces scoring is complicated, Kevin wants you to write a program to compute his final score.

Codeforces scores are computed as follows: If the maximum point value of a problem is x, and Kevin submitted correctly at minute m but made w wrong submissions, then his score on that problem is $$\max \left( 0.3x, \left( 1 - \frac{m}{250} \right)x - 50w \right)$$. His total score is equal to the sum of his scores for each problem. In addition, Kevin's total score gets increased by 100 points for each successful hack, but gets decreased by 50 points for each unsuccessful hack.

All arithmetic operations are performed with absolute precision and no rounding. It is guaranteed that Kevin's final score is an integer.

## Input Format
The first line of the input contains five space-separated integers m1, m2, m3, m4, m5, where mi (0 ≤ mi ≤ 119) is the time of Kevin's last submission for problem i. His last submission is always correct and gets accepted.

The second line contains five space-separated integers w1, w2, w3, w4, w5, where wi (0 ≤ wi ≤ 10) is Kevin's number of wrong submissions on problem i.

The last line contains two space-separated integers hs and hu (0 ≤ hs, hu ≤ 20), denoting the Kevin's numbers of successful and unsuccessful hacks, respectively.

## Output Format
Print a single integer, the value of Kevin's final score.

## Examples
```input
20 40 60 80 100
0 1 2 3 4
1 0
```
```output
4900
```
-----
```input
119 119 119 119 119
0 0 0 0 0
10 0
```
```output
4930
```

## Note
In the second sample, Kevin takes 119 minutes on all of the problems. Therefore, he gets $$( 1 - \frac { 1 1 9 } { 2 5 0 } ) = \frac { 1 3 1 } { 2 5 0 }$$ of the points on each problem. So his score from solving problems is $${ \frac { 1 3 1 } { 2 5 0 } } ( 5 0 0 + 1 0 0 0 + 1 5 0 0 + 2 0 0 0 + 2 5 0 0 ) = 3 9 3 0$$. Adding in 10·100 = 1000 points from hacks, his total score becomes 3930 + 1000 = 4930.

Now solve the problem and return the code.