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
On the way to Rio de Janeiro Ostap kills time playing with a grasshopper he took with him in a special box. Ostap builds a line of length n such that some cells of this line are empty and some contain obstacles. Then, he places his grasshopper to one of the empty cells and a small insect in another empty cell. The grasshopper wants to eat the insect.

Ostap knows that grasshopper is able to jump to any empty cell that is exactly k cells away from the current (to the left or to the right). Note that it doesn't matter whether intermediate cells are empty or not as the grasshopper makes a jump over them. For example, if k = 1 the grasshopper can jump to a neighboring cell only, and if k = 2 the grasshopper can jump over a single cell.

Your goal is to determine whether there is a sequence of jumps such that grasshopper will get from his initial position to the cell with an insect.

## Input Format
The first line of the input contains two integers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1) — the number of cells in the line and the length of one grasshopper's jump.

The second line contains a string of length n consisting of characters '.', '#', 'G' and 'T'. Character '.' means that the corresponding cell is empty, character '#' means that the corresponding cell contains an obstacle and grasshopper can't jump there. Character 'G' means that the grasshopper starts at this position and, finally, 'T' means that the target insect is located at this cell. It's guaranteed that characters 'G' and 'T' appear in this line exactly once.

## Output Format
If there exists a sequence of jumps (each jump of length k), such that the grasshopper can get from his initial position to the cell with the insect, print "YES" (without quotes) in the only line of the input. Otherwise, print "NO" (without quotes).

## Examples
```input
5 2
#G#T#
```
```output
YES
```
-----
```input
6 1
T....G
```
```output
YES
```
-----
```input
7 3
T..#..G
```
```output
NO
```
-----
```input
6 2
..GT..
```
```output
NO
```

## Note
In the first sample, the grasshopper can make one jump to the right in order to get from cell 2 to cell 4.

In the second sample, the grasshopper is only able to jump to neighboring cells but the way to the insect is free — he can get there by jumping left 5 times.

In the third sample, the grasshopper can't make a single jump.

In the fourth sample, the grasshopper can only jump to the cells with odd indices, thus he won't be able to reach the insect.

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
Bash wants to become a Pokemon master one day. Although he liked a lot of Pokemon, he has always been fascinated by Bulbasaur the most. Soon, things started getting serious and his fascination turned into an obsession. Since he is too young to go out and catch Bulbasaur, he came up with his own way of catching a Bulbasaur.

Each day, he takes the front page of the newspaper. He cuts out the letters one at a time, from anywhere on the front page of the newspaper to form the word "Bulbasaur" (without quotes) and sticks it on his wall. Bash is very particular about case — the first letter of "Bulbasaur" must be upper case and the rest must be lower case. By doing this he thinks he has caught one Bulbasaur. He then repeats this step on the left over part of the newspaper. He keeps doing this until it is not possible to form the word "Bulbasaur" from the newspaper.

Given the text on the front page of the newspaper, can you tell how many Bulbasaurs he will catch today?

Note: uppercase and lowercase letters are considered different.

## Input Format
Input contains a single line containing a string s (1  ≤  |s|  ≤  105) — the text on the front page of the newspaper without spaces and punctuation marks. |s| is the length of the string s.

The string s contains lowercase and uppercase English letters, i.e. $$s_i \in \{a,b,\ldots,z,A,B,\ldots,Z\}$$.

## Output Format
Output a single integer, the answer to the problem.

## Examples
```input
Bulbbasaur
```
```output
1
```
-----
```input
F
```
```output
0
```
-----
```input
aBddulbasaurrgndgbualdBdsagaurrgndbb
```
```output
2
```

## Note
In the first case, you could pick: Bulbbasaur.

In the second case, there is no way to pick even a single Bulbasaur.

In the third case, you can rearrange the string to BulbasaurBulbasauraddrgndgddgargndbb to get two words "Bulbasaur".

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
Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases.

But Zulu warns him that a group of k > 1 Pokemon with strengths {s1, s2, s3, ..., sk} tend to fight among each other if gcd(s1, s2, s3, ..., sk) = 1 (see notes for gcd definition).

Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take?

Note: A Pokemon cannot fight with itself.

## Input Format
The input consists of two lines.

The first line contains an integer n (1 ≤ n ≤ 105), the number of Pokemon in the lab.

The next line contains n space separated integers, where the i-th of them denotes si (1 ≤ si ≤ 105), the strength of the i-th Pokemon.

## Output Format
Print single integer — the maximum number of Pokemons Bash can take.

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

## Note
gcd (greatest common divisor) of positive integers set {a1, a2, ..., an} is the maximum positive integer that divides all the integers {a1, a2, ..., an}.

In the first sample, we can take Pokemons with strengths {2, 4} since gcd(2, 4) = 2.

In the second sample, we can take Pokemons with strengths {2, 4, 6}, and there is no larger group with gcd ≠ 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
Mahmoud has n line segments, the i-th of them has length ai. Ehab challenged him to use exactly 3 line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle.

Mahmoud should use exactly 3 line segments, he can't concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area.

## Input Format
The first line contains single integer n (3 ≤ n ≤ 105) — the number of line segments Mahmoud has.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the lengths of line segments Mahmoud has.

## Output Format
In the only line print "YES" if he can choose exactly three line segments and form a non-degenerate triangle with them, and "NO" otherwise.

## Examples
```input
5
1 5 3 2 4
```
```output
YES
```
-----
```input
3
4 1 2
```
```output
NO
```

## Note
For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle.

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
Given a positive integer n, find k integers (not necessary distinct) such that all these integers are strictly greater than 1, and their product is equal to n.

## Input Format
The first line contains two integers n and k (2 ≤ n ≤ 100000, 1 ≤ k ≤ 20).

## Output Format
If it's impossible to find the representation of n as a product of k numbers, print -1.

Otherwise, print k integers in any order. Their product must be equal to n. If there are multiple answers, print any of them.

## Examples
```input
100000 2
```
```output
2 50000
```
-----
```input
100000 20
```
```output
-1
```
-----
```input
1024 5
```
```output
2 64 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
You are given sequence a1, a2, ..., an of integer numbers of length n. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences. It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.

## Input Format
The first line contains integer number n (1 ≤ n ≤ 105).

The second line contains n integer numbers a1, a2, ..., an ( - 104 ≤ ai ≤ 104). The sequence contains at least one subsequence with odd sum.

## Output Format
Print sum of resulting subseqeuence.

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

## Note
In the first example sum of the second and the fourth elements is 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Petya recieved a gift of a string s with length up to 105 characters for his birthday. He took two more empty strings t and u and decided to play a game. This game has two possible moves:

- Extract the first character of s and append t with this character.
- Extract the last character of t and append u with this character.

Petya wants to get strings s and t empty and string u lexicographically minimal.

You should write a program that will help Petya win the game.

## Input Format
First line contains non-empty string s (1 ≤ |s| ≤ 105), consisting of lowercase English letters.

## Output Format
Print resulting string u.

## Examples
```input
cab
```
```output
abc
```
-----
```input
acdb
```
```output
abdc
```

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
Let T be arbitrary binary tree — tree, every vertex of which has no more than two children. Given tree is rooted, so there exists only one vertex which doesn't have a parent — it's the root of a tree. Every vertex has an integer number written on it. Following algorithm is run on every value from the tree T:

1. Set pointer to the root of a tree.
2. Return success if the value in the current vertex is equal to the number you are looking for
3. Go to the left child of the vertex if the value in the current vertex is greater than the number you are looking for
4. Go to the right child of the vertex if the value in the current vertex is less than the number you are looking for
5. Return fail if you try to go to the vertex that doesn't exist

Here is the pseudo-code of the described algorithm:

The described algorithm works correctly if the tree is binary search tree (i.e. for each node the values of left subtree are less than the value in the node, the values of right subtree are greater than the value in the node). But it can return invalid result if tree is not a binary search tree.

Since the given tree is not necessarily a binary search tree, not all numbers can be found this way. Your task is to calculate, how many times the search will fail being running on every value from the tree.

If the tree has multiple vertices with the same values on them then you should run algorithm on every one of them separately.

## Input Format
First line contains integer number n (1 ≤ n ≤ 105) — number of vertices in the tree.

Each of the next n lines contains 3 numbers v, l, r (0 ≤ v ≤ 109) — value on current vertex, index of the left child of the vertex and index of the right child of the vertex, respectively. If some child doesn't exist then number  - 1 is set instead. Note that different vertices of the tree may contain the same values.

## Output Format
Print number of times when search algorithm will fail.

## Examples
```input
3
15 -1 -1
10 1 3
5 -1 -1
```
```output
2
```
-----
```input
8
6 2 3
3 4 5
12 6 7
1 -1 8
4 -1 -1
5 -1 -1
14 -1 -1
2 -1 -1
```
```output
1
```

## Note
In the example the root of the tree in vertex 2. Search of numbers 5 and 15 will return fail because on the first step algorithm will choose the subtree which doesn't contain numbers you are looking for.

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

# Problem
One day Masha came home and noticed n mice in the corridor of her flat. Of course, she shouted loudly, so scared mice started to run to the holes in the corridor.

The corridor can be represeted as a numeric axis with n mice and m holes on it. ith mouse is at the coordinate xi, and jth hole — at coordinate pj. jth hole has enough room for cj mice, so not more than cj mice can enter this hole.

What is the minimum sum of distances that mice have to go through so that they all can hide in the holes? If ith mouse goes to the hole j, then its distance is |xi - pj|.

Print the minimum sum of distances.

## Input Format
The first line contains two integer numbers n, m (1 ≤ n, m ≤ 5000) — the number of mice and the number of holes, respectively.

The second line contains n integers x1, x2, ..., xn ( - 109 ≤ xi ≤ 109), where xi is the coordinate of ith mouse.

Next m lines contain pairs of integer numbers pj, cj ( - 109 ≤ pj ≤ 109, 1 ≤ cj ≤ 5000), where pj is the coordinate of jth hole, and cj is the maximum number of mice that can hide in the hole j.

## Output Format
Print one integer number — the minimum sum of distances. If there is no solution, print -1 instead.

## Examples
```input
4 5
6 2 8 9
3 6
2 1
3 6
4 7
4 7
```
```output
11
```
-----
```input
7 2
10 20 30 40 50 45 35
-1000000000 10
1000000000 1
```
```output
7000000130
```

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
Polycarp is very careful. He even types numeric sequences carefully, unlike his classmates. If he sees a sequence without a space after the comma, with two spaces in a row, or when something else does not look neat, he rushes to correct it. For example, number sequence written like "1,2 ,3,...,   10" will be corrected to "1, 2, 3, ..., 10".

In this task you are given a string s, which is composed by a concatination of terms, each of which may be:

- a positive integer of an arbitrary length (leading zeroes are not allowed),
- a "comma" symbol (","),
- a "space" symbol (" "),
- "three dots" ("...", that is, exactly three points written one after another, also known as suspension points).

Polycarp wants to add and remove spaces in the string s to ensure the following:

- each comma is followed by exactly one space (if the comma is the last character in the string, this rule does not apply to it),
- each "three dots" term is preceded by exactly one space (if the dots are at the beginning of the string, this rule does not apply to the term),
- if two consecutive numbers were separated by spaces only (one or more), then exactly one of them should be left,
- there should not be other spaces.

Automate Polycarp's work and write a program that will process the given string s.

## Input Format
The input data contains a single string s. Its length is from 1 to 255 characters. The string s does not begin and end with a space. Its content matches the description given above.

## Output Format
Print the string s after it is processed. Your program's output should be exactly the same as the expected answer. It is permissible to end output line with a line-break character, and without it.

## Examples
```input
1,2 ,3,...,     10
```
```output
1, 2, 3, ..., 10
```
-----
```input
1,,,4...5......6
```
```output
1, , , 4 ...5 ... ...6
```
-----
```input
...,1,2,3,...
```
```output
..., 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 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
Polycarp loves not only to take pictures, but also to show his photos to friends. On his personal website he has recently installed a widget that can display n photos with the scroll option. At each moment of time the widget displays exactly one photograph with the option showing the previous/next one. From the first photo, you can switch to the second one or to the n-th one, from the second photo you can switch to the third one or to the first one, etc. Thus, navigation is performed in a cycle.

Polycarp's collection consists of m photo albums, the i-th album contains ai photos. Polycarp wants to choose n photos and put them on a new widget. To make watching the photos interesting to the visitors, he is going to post pictures so that no two photos from one album were neighboring (each photo will have exactly two neighbors, the first photo's neighbors are the second and the n-th one).

Help Polycarp compile a photo gallery. Select n photos from his collection and put them in such order that no two photos from one album went one after the other.

## Input Format
The first line contains two integers n and m (3 ≤ n ≤ 1000, 1 ≤ m ≤ 40), where n is the number of photos on the widget, and m is the number of albums. The second line contains m integers a1, a2, ..., am (1 ≤ ai ≤ 1000), where ai is the number of photos in the i-th album.

## Output Format
Print the single number -1 if there is no solution. Otherwise, print n numbers t1, t2, ..., tn, where ti represents the number of the album of the i-th picture in the widget. The albums are numbered from 1 in the order of their appearance in the input. If there are several solutions, print any of them.

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

Now solve the problem and return the code.