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

# Problem
Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change one arbitrary character Ai in one of the strings into arbitrary character Bi, but he has to pay for every move a particular sum of money, equal to Wi. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings.

## Input Format
The first input line contains two initial non-empty strings s and t, consisting of lower case Latin letters. The length of each string doesn't exceed 105. The following line contains integer n (0 ≤ n ≤ 500) — amount of possible changings. Then follow n lines, each containing characters Ai and Bi (lower case Latin letters) and integer Wi (0 ≤ Wi ≤ 100), saying that it's allowed to change character Ai into character Bi in any of the strings and spend sum of money Wi.

## Output Format
If the answer exists, output the answer to the problem, and the resulting string. Otherwise output -1 in the only line. If the answer is not unique, output any.

## Examples
```input
uayd
uxxd
3
a x 8
x y 13
d c 3
```
```output
21
uxyd
```
-----
```input
a
b
3
a b 2
a b 3
b a 5
```
```output
2
b
```
-----
```input
abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0
```
```output
-1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Learn, learn and learn again — Valera has to do this every day. He is studying at mathematical school, where math is the main discipline. The mathematics teacher loves her discipline very much and tries to cultivate this love in children. That's why she always gives her students large and difficult homework. Despite that Valera is one of the best students, he failed to manage with the new homework. That's why he asks for your help. He has the following task. A sequence of n numbers is given. A prefix of a sequence is the part of the sequence (possibly empty), taken from the start of the sequence. A suffix of a sequence is the part of the sequence (possibly empty), taken from the end of the sequence. It is allowed to sequentially make two operations with the sequence. The first operation is to take some prefix of the sequence and multiply all numbers in this prefix by  - 1. The second operation is to take some suffix and multiply all numbers in it by  - 1. The chosen prefix and suffix may intersect. What is the maximum total sum of the sequence that can be obtained by applying the described operations?

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — amount of elements in the sequence. The second line contains n integers ai ( - 104 ≤ ai ≤ 104) — the sequence itself.

## Output Format
The first and the only line of the output should contain the answer to the problem.

## Examples
```input
3
-1 -2 -3
```
```output
6
```
-----
```input
5
-4 2 0 5 0
```
```output
11
```
-----
```input
5
-1 10 -5 10 -2
```
```output
18
```

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
Berland is facing dark times again. The army of evil lord Van de Mart is going to conquer the whole kingdom. To the council of war called by the Berland's king Valery the Severe came n knights. After long discussions it became clear that the kingdom has exactly n control points (if the enemy conquers at least one of these points, the war is lost) and each knight will occupy one of these points.

Berland is divided into m + 1 regions with m fences, and the only way to get from one region to another is to climb over the fence. Each fence is a circle on a plane, no two fences have common points, and no control point is on the fence. You are given k pairs of numbers ai, bi. For each pair you have to find out: how many fences a knight from control point with index ai has to climb over to reach control point bi (in case when Van de Mart attacks control point bi first). As each knight rides a horse (it is very difficult to throw a horse over a fence), you are to find out for each pair the minimum amount of fences to climb over.

## Input Format
The first input line contains three integers n, m, k (1 ≤ n, m ≤ 1000, 0 ≤ k ≤ 100000). Then follow n lines, each containing two integers Kxi, Kyi ( - 109 ≤ Kxi, Kyi ≤ 109) — coordinates of control point with index i. Control points can coincide.

Each of the following m lines describes fence with index i with three integers ri, Cxi, Cyi (1 ≤ ri ≤ 109,  - 109 ≤ Cxi, Cyi ≤ 109) — radius and center of the circle where the corresponding fence is situated.

Then follow k pairs of integers ai, bi (1 ≤ ai, bi ≤ n), each in a separate line — requests that you have to answer. ai and bi can coincide.

## Output Format
Output exactly k lines, each containing one integer — the answer to the corresponding request.

## Examples
```input
2 1 1
0 0
3 3
2 0 0
1 2
```
```output
1
```
-----
```input
2 3 1
0 0
4 4
1 0 0
2 0 0
3 0 0
1 2
```
```output
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
A country has n cities. Initially, there is no road in the country. One day, the king decides to construct some roads connecting pairs of cities. Roads can be traversed either way. He wants those roads to be constructed in such a way that it is possible to go from each city to any other city by traversing at most two roads. You are also given m pairs of cities — roads cannot be constructed between these pairs of cities.

Your task is to construct the minimum number of roads that still satisfy the above conditions. The constraints will guarantee that this is always possible.

## Input Format
The first line consists of two integers n and m $$( 1 \leq n \leq 1 0 ^ { 3 }, 0 \leq m < \frac { n } { 2 } )$$.

Then m lines follow, each consisting of two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), which means that it is not possible to construct a road connecting cities ai and bi. Consider the cities are numbered from 1 to n.

It is guaranteed that every pair of cities will appear at most once in the input.

## Output Format
You should print an integer s: the minimum number of roads that should be constructed, in the first line. Then s lines should follow, each consisting of two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), which means that a road should be constructed between cities ai and bi.

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

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

## Note
This is one possible solution of the example:

These are examples of wrong solutions:

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
Gerald has n younger brothers and their number happens to be even. One day he bought n2 candy bags. One bag has one candy, one bag has two candies, one bag has three candies and so on. In fact, for each integer k from 1 to n2 he has exactly one bag with k candies.

Help him give n bags of candies to each brother so that all brothers got the same number of candies.

## Input Format
The single line contains a single integer n (n is even, 2 ≤ n ≤ 100) — the number of Gerald's brothers.

## Output Format
Let's assume that Gerald indexes his brothers with numbers from 1 to n. You need to print n lines, on the i-th line print n integers — the numbers of candies in the bags for the i-th brother. Naturally, all these numbers should be distinct and be within limits from 1 to n2. You can print the numbers in the lines in any order.

It is guaranteed that the solution exists at the given limits.

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

## Note
The sample shows Gerald's actions if he has two brothers. In this case, his bags contain 1, 2, 3 and 4 candies. He can give the bags with 1 and 4 candies to one brother and the bags with 2 and 3 to the other brother.

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
Gerald is very particular to eight point sets. He thinks that any decent eight point set must consist of all pairwise intersections of three distinct integer vertical straight lines and three distinct integer horizontal straight lines, except for the average of these nine points. In other words, there must be three integers x1, x2, x3 and three more integers y1, y2, y3, such that x1 < x2 < x3, y1 < y2 < y3 and the eight point set consists of all points (xi, yj) (1 ≤ i, j ≤ 3), except for point (x2, y2).

You have a set of eight points. Find out if Gerald can use this set?

## Input Format
The input consists of eight lines, the i-th line contains two space-separated integers xi and yi (0 ≤ xi, yi ≤ 106). You do not have any other conditions for these points.

## Output Format
In a single line print word "respectable", if the given set of points corresponds to Gerald's decency rules, and "ugly" otherwise.

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

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
Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on.

Iahub has the following scheme of painting: he skips x - 1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y - 1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.

After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question.

## Input Format
The input will have a single line containing four integers in this order: x, y, a, b. (1 ≤ x, y ≤ 1000, 1 ≤ a, b ≤ 2·109, a ≤ b).

## Output Format
Output a single integer — the number of bricks numbered no less than a and no greater than b that are painted both red and pink.

## Examples
```input
2 3 6 18
```
```output
3
```

## Note
Let's look at the bricks from a to b (a = 6, b = 18). The bricks colored in red are numbered 6, 8, 10, 12, 14, 16, 18. The bricks colored in pink are numbered 6, 9, 12, 15, 18. The bricks colored in both red and pink are numbered with 6, 12 and 18.

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
Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.

## Input Format
The first line contains integer n (4 ≤ n ≤ 300). Each of the next n lines contains two integers: xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide.

## Output Format
Output a single real number — the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10 - 9.

## Examples
```input
5
0 0
0 4
4 0
4 4
2 3
```
```output
16.000000
```

## Note
In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4·4 = 16.

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
When you were a child you must have been told a puzzle of bags and coins. Anyway, here's one of its versions:

A horse has three bags. The first bag has one coin, the second bag has one coin and the third bag has three coins. In total, the horse has three coins in the bags. How is that possible?

The answer is quite simple. The third bag contains a coin and two other bags.

This problem is a generalization of the childhood puzzle. You have n bags. You know that the first bag contains a1 coins, the second bag contains a2 coins, ..., the n-th bag contains an coins. In total, there are s coins. Find the way to arrange the bags and coins so that they match the described scenario or else state that it is impossible to do.

## Input Format
The first line contains two integers n and s (1 ≤ n, s ≤ 70000) — the number of bags and the total number of coins. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 70000), where ai shows the number of coins in the i-th bag.

## Output Format
If the answer doesn't exist, print -1.

Otherwise, print n lines, on the i-th line print the contents of the i-th bag. The first number in the line, ci (0 ≤ ci ≤ ai), must represent the number of coins lying directly in the i-th bag (the coins in the bags that are in the i-th bag are not taken into consideration). The second number in the line, ki (0 ≤ ki < n) must represent the number of bags that lie directly in the i-th bag (the bags that are inside the bags lying in the i-th bag are not taken into consideration). Next, the line must contain ki integers — the numbers of the bags that are lying directly in the i-th bag.

The total number of coins in the solution must equal s. If we count the total number of coins the i-th bag in the solution has, we should get ai.

No bag can directly lie in more than one bag. The bags can be nested in more than one level (see the second test case). If there are multiple correct answers, you can print any of them.

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

## Note
The pictures below show two possible ways to solve one test case from the statement. The left picture corresponds to the first test case, the right picture corresponds to the second one.

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
Xenia the coder went to The Olympiad of Informatics and got a string problem. Unfortunately, Xenia isn't fabulous in string algorithms. Help her solve the problem.

String s is a sequence of characters s1s2... s|s|, where record |s| shows the length of the string.

Substring s[i... j] of string s is string sisi + 1... sj.

String s is a Gray string, if it meets the conditions:

- the length of string |s| is odd;
- character $$S^{\frac{|s|+1}{2}}$$ occurs exactly once in the string;
- either |s| = 1, or substrings $$s[1 \ldots \frac{|s|+1}{2}-1]$$ and $$s \left[ \frac{|s|+1}{2} + 1 \ldots |s| \right]$$ are the same and are Gray strings.

For example, strings "abacaba", "xzx", "g" are Gray strings and strings "aaa", "xz", "abaxcbc" are not.

The beauty of string p is the sum of the squares of the lengths of all substrings of string p that are Gray strings. In other words, consider all pairs of values i, j (1 ≤ i ≤ j ≤ |p|). If substring p[i... j] is a Gray string, you should add (j - i + 1)2 to the beauty.

Xenia has got string t consisting of lowercase English letters. She is allowed to replace at most one letter of the string by any other English letter. The task is to get a string of maximum beauty.

## Input Format
The first line contains a non-empty string t (1 ≤ |t| ≤ 105). String t only consists of lowercase English letters.

## Output Format
Print the sought maximum beauty value Xenia can get.

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
zzz
```
```output
12
```
-----
```input
aba
```
```output
12
```
-----
```input
abacaba
```
```output
83
```
-----
```input
aaaaaa
```
```output
15
```

## Note
In the first test sample the given string can be transformed into string p = "zbz". Such string contains Gray strings as substrings p[1... 1], p[2... 2], p[3... 3] и p[1... 3]. In total, the beauty of string p gets equal to 12 + 12 + 12 + 32 = 12. You can't obtain a more beautiful string.

In the second test case it is not necessary to perform any operation. The initial string has the maximum possible beauty.

Now solve the problem and return the code.