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
Polycarpus plays with red and blue marbles. He put n marbles from the left to the right in a row. As it turned out, the marbles form a zebroid.

A non-empty sequence of red and blue marbles is a zebroid, if the colors of the marbles in this sequence alternate. For example, sequences (red; blue; red) and (blue) are zebroids and sequence (red; red) is not a zebroid.

Now Polycarpus wonders, how many ways there are to pick a zebroid subsequence from this sequence. Help him solve the problem, find the number of ways modulo 1000000007 (109 + 7).

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 106) — the number of marbles in Polycarpus's sequence.

## Output Format
Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

## Examples
```input
3
```
```output
6
```
-----
```input
4
```
```output
11
```

## Note
Let's consider the first test sample. Let's assume that Polycarpus initially had sequence (red; blue; red), so there are six ways to pick a zebroid:

- pick the first marble;
- pick the second marble;
- pick the third marble;
- pick the first and second marbles;
- pick the second and third marbles;
- pick the first, second and third marbles.

It can be proven that if Polycarpus picks (blue; red; blue) as the initial sequence, the number of ways won't change.

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
Flatland is inhabited by pixels of three colors: red, green and blue. We know that if two pixels of different colors meet in a violent fight, only one of them survives the fight (that is, the total number of pixels decreases by one). Besides, if pixels of colors x and y (x ≠ y) meet in a violent fight, then the pixel that survives the fight immediately changes its color to z (z ≠ x; z ≠ y). Pixels of the same color are friends, so they don't fight.

The King of Flatland knows that his land will be peaceful and prosperous when the pixels are of the same color. For each of the three colors you know the number of pixels of this color that inhabit Flatland. Help the king and determine whether fights can bring peace and prosperity to the country and if it is possible, find the minimum number of fights needed to make the land peaceful and prosperous.

## Input Format
The first line contains three space-separated integers a, b and c (0 ≤ a, b, c ≤ 231; a + b + c > 0) — the number of red, green and blue pixels, correspondingly.

## Output Format
Print a single number — the minimum number of pixel fights before the country becomes peaceful and prosperous. If making the country peaceful and prosperous is impossible, print -1.

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

## Note
In the first test sample the country needs only one fight to achieve peace and prosperity. Besides, it can be any fight whatsoever. For example, let's assume that the green and the blue pixels fight, then the surviving pixel will be red. As a result, after the fight there are two red pixels. There won't be other pixels.

In the second sample the following sequence of fights is possible: red and blue, green and red, red and blue. As a result, after all fights there is one green pixel left.

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

# Problem
Vasya went for a walk in the park. The park has n glades, numbered from 1 to n. There are m trails between the glades. The trails are numbered from 1 to m, where the i-th trail connects glades xi and yi. The numbers of the connected glades may be the same (xi = yi), which means that a trail connects a glade to itself. Also, two glades may have several non-intersecting trails between them.

Vasya is on glade 1, he wants to walk on all trails of the park exactly once, so that he can eventually return to glade 1. Unfortunately, Vasya does not know whether this walk is possible or not. Help Vasya, determine whether the walk is possible or not. If such walk is impossible, find the minimum number of trails the authorities need to add to the park in order to make the described walk possible.

Vasya can shift from one trail to another one only on glades. He can move on the trails in both directions. If Vasya started going on the trail that connects glades a and b, from glade a, then he must finish this trail on glade b.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 106; 0 ≤ m ≤ 106) — the number of glades in the park and the number of trails in the park, respectively. Next m lines specify the trails. The i-th line specifies the i-th trail as two space-separated numbers, xi, yi (1 ≤ xi, yi ≤ n) — the numbers of the glades connected by this trail.

## Output Format
Print the single integer — the answer to the problem. If Vasya's walk is possible without adding extra trails, print 0, otherwise print the minimum number of trails the authorities need to add to the park in order to make Vasya's walk possible.

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

## Note
In the first test case the described walk is possible without building extra trails. For example, let's first go on the first trail, then on the second one, and finally on the third one.

In the second test case the described walk is impossible without adding extra trails. To make the walk possible, it is enough to add one trail, for example, between glades number one and two.

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

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

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

Execution time limit: 0.5 seconds
Memory limit: 256.0 MB

# Problem
Jabber ID on the national Berland service «Babber» has a form <username>@<hostname>[/resource], where

- <username> — is a sequence of Latin letters (lowercase or uppercase), digits or underscores characters «_», the length of <username> is between 1 and 16, inclusive.
- <hostname> — is a sequence of word separated by periods (characters «.»), where each word should contain only characters allowed for <username>, the length of each word is between 1 and 16, inclusive. The length of <hostname> is between 1 and 32, inclusive.
- <resource> — is a sequence of Latin letters (lowercase or uppercase), digits or underscores characters «_», the length of <resource> is between 1 and 16, inclusive.

The content of square brackets is optional — it can be present or can be absent.

There are the samples of correct Jabber IDs: [email protected], [email protected]/contest.

Your task is to write program which checks if given string is a correct Jabber ID.

## Input Format
The input contains of a single line. The line has the length between 1 and 100 characters, inclusive. Each characters has ASCII-code between 33 and 127, inclusive.

## Output Format
Print YES or NO.

## Examples
```input
[email protected]
```
```output
YES
```
-----
```input
[email protected]
/contest.icpc/12
```
```output
NO
```

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 two set of points. The first set is determined by the equation A1x + B1y + C1 = 0, and the second one is determined by the equation A2x + B2y + C2 = 0.

Write the program which finds the number of points in the intersection of two given sets.

## Input Format
The first line of the input contains three integer numbers A1, B1, C1 separated by space. The second line contains three integer numbers A2, B2, C2 separated by space. All the numbers are between -100 and 100, inclusive.

## Output Format
Print the number of points in the intersection or -1 if there are infinite number of points.

## Examples
```input
1 1 0
2 2 0
```
```output
-1
```
-----
```input
1 1 0
2 -2 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: 1.0 seconds
Memory limit: 64.0 MB

# Problem
Once Bob took a paper stripe of n squares (the height of the stripe is 1 square). In each square he wrote an integer number, possibly negative. He became interested in how many ways exist to cut this stripe into three pieces so that the sum of numbers from each piece is equal to the sum of numbers from any other piece, and each piece contains positive integer amount of squares. Would you help Bob solve this problem?

## Input Format
The first input line contains integer n (1 ≤ n ≤ 105) — amount of squares in the stripe. The second line contains n space-separated numbers — they are the numbers written in the squares of the stripe. These numbers are integer and do not exceed 10000 in absolute value.

## Output Format
Output the amount of ways to cut the stripe into three non-empty pieces so that the sum of numbers from each piece is equal to the sum of numbers from any other piece. Don't forget that it's allowed to cut the stripe along the squares' borders only.

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

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

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

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

Execution time limit: 0.5 seconds
Memory limit: 64.0 MB

# Problem
You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

## Input Format
The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.

## Output Format
Output minimal cycle length or -1 if it doesn't exists.

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

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
The Little Elephant is playing with the Cartesian coordinates' system. Most of all he likes playing with integer points. The Little Elephant defines an integer point as a pair of integers (x; y), such that 0 ≤ x ≤ w and 0 ≤ y ≤ h. Thus, the Little Elephant knows only (w + 1)·(h + 1) distinct integer points.

The Little Elephant wants to paint a triangle with vertexes at integer points, the triangle's area must be a positive integer. For that, he needs to find the number of groups of three points that form such triangle. At that, the order of points in a group matters, that is, the group of three points (0;0), (0;2), (2;2) isn't equal to the group (0;2), (0;0), (2;2).

Help the Little Elephant to find the number of groups of three integer points that form a nondegenerate triangle with integer area.

## Input Format
A single line contains two integers w and h (1 ≤ w, h ≤ 4000).

## Output Format
In a single output line print an integer — the remainder of dividing the answer to the problem by 1000000007 (109 + 7).

## Examples
```input
2 1
```
```output
36
```
-----
```input
2 2
```
```output
240
```

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 soluton must read input from the file 'input.txt' and write output to the file 'output.txt'.
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
One fine October day a mathematics teacher Vasily Petrov went to a class and saw there n pupils who sat at the $$\frac{\pi}{2}$$ desks, two people at each desk. Vasily quickly realized that number n is even. Like all true mathematicians, Vasily has all students numbered from 1 to n.

But Vasily Petrov did not like the way the children were seated at the desks. According to him, the students whose numbers differ by 1, can not sit together, as they talk to each other all the time, distract others and misbehave.

On the other hand, if a righthanded student sits at the left end of the desk and a lefthanded student sits at the right end of the desk, they hit elbows all the time and distract each other. In other cases, the students who sit at the same desk, do not interfere with each other.

Vasily knows very well which students are lefthanders and which ones are righthanders, and he asks you to come up with any order that meets these two uncomplicated conditions (students do not talk to each other and do not bump their elbows). It is guaranteed that the input is such that at least one way to seat the students always exists.

## Input Format
The first input line contains a single even integer n (4 ≤ n ≤ 100) — the number of students in the class. The second line contains exactly n capital English letters "L" and "R". If the i-th letter at the second line equals "L", then the student number i is a lefthander, otherwise he is a righthander.

## Output Format
Print $$\frac{\pi}{2}$$ integer pairs, one pair per line. In the i-th line print the numbers of students that will sit at the i-th desk. The first number in the pair stands for the student who is sitting to the left, and the second number stands for the student who is sitting to the right. Separate the numbers in the pairs by spaces. If there are multiple solutions, print any of them.

## Examples
```input
6
LLRLLL
```
```output
1 4
2 5
6 3
```
-----
```input
4
RRLL
```
```output
3 1
4 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 soluton must read input from the file 'input.txt' and write output to the file 'output.txt'.
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
Vasya is going to the Olympics in the city Ntown by train. The boy wants to read the textbook to prepare for the Olympics. He counted that he needed k hours for this. He also found that the light in the train changes every hour. The light is measured on a scale from 0 to 100, where 0 is very dark, and 100 is very light.

Vasya has a train lighting schedule for all n hours of the trip — n numbers from 0 to 100 each (the light level in the first hour, the second hour and so on). During each of those hours he will either read the whole time, or not read at all. He wants to choose k hours to read a book, not necessarily consecutive, so that the minimum level of light among the selected hours were maximum. Vasya is very excited before the upcoming contest, help him choose reading hours.

## Input Format
The first input line contains two integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n) — the number of hours on the train and the number of hours to read, correspondingly. The second line contains n space-separated integers ai (0 ≤ ai ≤ 100), ai is the light level at the i-th hour.

## Output Format
In the first output line print the minimum light level Vasya will read at. In the second line print k distinct space-separated integers b1, b2, ..., bk, — the indexes of hours Vasya will read at (1 ≤ bi ≤ n). The hours are indexed starting from 1. If there are multiple optimal solutions, print any of them. Print the numbers bi in an arbitrary order.

## Examples
```input
5 3
20 10 30 40 10
```
```output
20
1 3 4
```
-----
```input
6 5
90 20 35 40 60 100
```
```output
35
1 3 4 5 6
```

## Note
In the first sample Vasya should read at the first hour (light 20), third hour (light 30) and at the fourth hour (light 40). The minimum light Vasya will have to read at is 20.

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
There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts.

- Current character pointer (CP);
- Direction pointer (DP) which can point left or right;

Initially CP points to the leftmost character of the sequence and DP points to the right.

We repeat the following steps until the first moment that CP points to somewhere outside the sequence.

- If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was 0 then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one.
- If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence.

If at any moment the CP goes outside of the sequence the execution is terminated.

It's obvious the every program in this language terminates after some steps.

We have a sequence s1, s2, ..., sn of "<", ">" and digits. You should answer q queries. Each query gives you l and r and asks how many of each digit will be printed if we run the sequence sl, sl + 1, ..., sr as an independent program in this language.

## Input Format
The first line of input contains two integers n and q (1 ≤ n, q ≤ 105) — represents the length of the sequence s and the number of queries.

The second line contains s, a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of s are not separated with spaces.

The next q lines each contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

## Output Format
For each query print 10 space separated integers: x0, x1, ..., x9 where xi equals the number of times the interpreter prints i while running the corresponding program. Print answers to the queries in the order they are given in input.

## Examples
```input
7 4
1>3>22<
1 3
4 7
7 7
1 7
```
```output
0 1 0 1 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
2 3 2 1 0 0 0 0 0 0
```

Now solve the problem and return the code.