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
Valera has got a rectangle table consisting of n rows and m columns. Valera numbered the table rows starting from one, from top to bottom and the columns – starting from one, from left to right. We will represent cell that is on the intersection of row x and column y by a pair of integers (x, y).

Valera wants to place exactly k tubes on his rectangle table. A tube is such sequence of table cells (x1, y1), (x2, y2), ..., (xr, yr), that:

- r ≥ 2;
- for any integer i (1 ≤ i ≤ r - 1) the following equation |xi - xi + 1| + |yi - yi + 1| = 1 holds;
- each table cell, which belongs to the tube, must occur exactly once in the sequence.

Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled:

- no pair of tubes has common cells;
- each cell of the table belongs to some tube.

Help Valera to arrange k tubes on his rectangle table in a fancy manner.

## Input Format
The first line contains three space-separated integers n, m, k (2 ≤ n, m ≤ 300; 2 ≤ 2k ≤ n·m) — the number of rows, the number of columns and the number of tubes, correspondingly.

## Output Format
Print k lines. In the i-th line print the description of the i-th tube: first print integer ri (the number of tube cells), then print 2ri integers xi1, yi1, xi2, yi2, ..., xiri, yiri (the sequence of table cells).

If there are multiple solutions, you can print any of them. It is guaranteed that at least one solution exists.

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

## Note
Picture for the first sample:

Picture for the second sample:

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
A permutation p of length n is a sequence of distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n). A permutation is an identity permutation, if for any i the following equation holds pi = i.

A swap (i, j) is the operation that swaps elements pi and pj in the permutation. Let's assume that f(p) is the minimum number of swaps that you need to make the permutation p an identity permutation.

Valera wonders, how he can transform permutation p into any permutation q, such that f(q) = m, using the minimum number of swaps. Help him do that.

## Input Format
The first line contains integer n (1 ≤ n ≤ 3000) — the length of permutation p. The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — Valera's initial permutation. The last line contains integer m (0 ≤ m < n).

## Output Format
In the first line, print integer k — the minimum number of swaps.

In the second line, print 2k integers x1, x2, ..., x2k — the description of the swap sequence. The printed numbers show that you need to consecutively make swaps (x1, x2), (x3, x4), ..., (x2k - 1, x2k).

If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.

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

## Note
Sequence x1, x2, ..., xs is lexicographically smaller than sequence y1, y2, ..., ys, if there is such integer r (1 ≤ r ≤ s), that x1 = y1, x2 = y2, ..., xr - 1 = yr - 1 and xr < yr.

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
Valera is a coder. Recently he wrote a funny program. The pseudo code for this program is given below:

Now Valera wonders: given the values x, k and p, what is the expected value of the resulting number s?

## Input Format
The first line of the input contains three integers x, k, p (1 ≤ x ≤ 109; 1 ≤ k ≤ 200; 0 ≤ p ≤ 100).

## Output Format
Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

## Examples
```input
1 1 50
```
```output
1.0000000000000
```
-----
```input
5 3 0
```
```output
3.0000000000000
```
-----
```input
5 3 25
```
```output
1.9218750000000
```

## Note
If the concept of expected value is new to you, you can read about it by the link:

http://en.wikipedia.org/wiki/Expected_value

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
DZY loves chessboard, and he enjoys playing with it.

He has a chessboard of n rows and m columns. Some cells of the chessboard are bad, others are good. For every good cell, DZY wants to put a chessman on it. Each chessman is either white or black. After putting all chessmen, DZY wants that no two chessmen with the same color are on two adjacent cells. Two cells are adjacent if and only if they share a common edge.

You task is to find any suitable placement of chessmen on the given chessboard.

## Input Format
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100).

Each of the next n lines contains a string of m characters: the j-th character of the i-th string is either "." or "-". A "." means that the corresponding cell (in the i-th row and the j-th column) is good, while a "-" means it is bad.

## Output Format
Output must contain n lines, each line must contain a string of m characters. The j-th character of the i-th string should be either "W", "B" or "-". Character "W" means the chessman on the cell is white, "B" means it is black, "-" means the cell is a bad cell.

If multiple answers exist, print any of them. It is guaranteed that at least one answer exists.

## Examples
```input
1 1
.
```
```output
B
```
-----
```input
2 2
..
..
```
```output
BW
WB
```
-----
```input
3 3
.-.
---
--.
```
```output
B-B
---
--B
```

## Note
In the first sample, DZY puts a single black chessman. Of course putting a white one is also OK.

In the second sample, all 4 cells are good. No two same chessmen share an edge in the sample output.

In the third sample, no good cells are adjacent. So you can just put 3 chessmen, no matter what their colors are.

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
DZY loves chemistry, and he enjoys mixing chemicals.

DZY has n chemicals, and m pairs of them will react. He wants to pour these chemicals into a test tube, and he needs to pour them in one by one, in any order.

Let's consider the danger of a test tube. Danger of an empty test tube is 1. And every time when DZY pours a chemical, if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by 2. Otherwise the danger remains as it is.

Find the maximum possible danger after pouring all the chemicals one by one in optimal order.

## Input Format
The first line contains two space-separated integers n and m $$( 1 \leq n \leq 50 ; \; 0 \leq m \leq \frac { n ( n - 1 ) } { 2 } )$$.

Each of the next m lines contains two space-separated integers xi and yi (1 ≤ xi < yi ≤ n). These integers mean that the chemical xi will react with the chemical yi. Each pair of chemicals will appear at most once in the input.

Consider all the chemicals numbered from 1 to n in some order.

## Output Format
Print a single integer — the maximum possible danger.

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

## Note
In the first sample, there's only one way to pour, and the danger won't increase.

In the second sample, no matter we pour the 1st chemical first, or pour the 2nd chemical first, the answer is always 2.

In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).

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
Today Vasya visited a widely known site and learned that the continuation of his favourite game Codecraft II will appear after exactly k months. He looked at the calendar and learned that at the moment is the month number s. Vasya immediately got interested in what month Codecraft III will appear. Help him understand that.

All the twelve months in Vasya's calendar are named using their usual English names: January, February, March, April, May, June, July, August, September, October, November, December.

## Input Format
The first input line contains the name of the current month. It is guaranteed that it is a proper English name of one of twelve months. The first letter is uppercase, the rest are lowercase. The second line contains integer k (0 ≤ k ≤ 100) — the number of months left till the appearance of Codecraft III.

## Output Format
Print starting from an uppercase letter the name of the month in which the continuation of Codeforces II will appear. The printed name must be contained in the list January, February, March, April, May, June, July, August, September, October, November, December.

## Examples
```input
November
3
```
```output
February
```
-----
```input
May
24
```
```output
May
```

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 are n students studying in the 6th grade, in group "B" of a berland secondary school. Every one of them has exactly one friend whom he calls when he has some news. Let us denote the friend of the person number i by g(i). Note that the friendships are not mutual, i.e. g(g(i)) is not necessarily equal to i.

On day i the person numbered as ai learns the news with the rating of bi (bi ≥ 1). He phones the friend immediately and tells it. While he is doing it, the news becomes old and its rating falls a little and becomes equal to bi - 1. The friend does the same thing — he also calls his friend and also tells the news. The friend of the friend gets the news already rated as bi - 2. It all continues until the rating of the news reaches zero as nobody wants to tell the news with zero rating.

More formally, everybody acts like this: if a person x learns the news with a non-zero rating y, he calls his friend g(i) and his friend learns the news with the rating of y - 1 and, if it is possible, continues the process.

Let us note that during a day one and the same person may call his friend and tell him one and the same news with different ratings. Thus, the news with the rating of bi will lead to as much as bi calls.

Your task is to count the values of resi — how many students learned their first news on day i.

The values of bi are known initially, whereas ai is determined from the following formula:

$$a_{i} = \left( (v_{i} + res_{i-1} - 1) \mod n \right) + 1,$$

## Input Format
The first line contains two space-separated integers n and m (2 ≤ n, m ≤ 105) — the number of students and the number of days. The second line contains n space-separated integers g(i) (1 ≤ g(i) ≤ n, g(i) ≠ i) — the number of a friend of the i-th student. The third line contains m space-separated integers vi (1 ≤ vi ≤ 107). The fourth line contains m space-separated integers bi (1 ≤ bi ≤ 107).

## Output Format
Print m lines containing one number each. The i-th line should contain resi — for what number of students the first news they've learned over the m days in question, was the news number i. The number of the news is the number of the day on which it can be learned. The days are numbered starting from one in the order in which they are given in the input file. Don't output res0.

## Examples
```input
3 4
2 3 1
1 2 3 4
1 2 3 4
```
```output
1
1
1
0
```
-----
```input
8 6
7 6 4 2 3 5 5 7
10 4 3 8 9 1
1 1 1 2 2 2
```
```output
1
1
1
2
1
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
There are n people taking dancing lessons. Every person is characterized by his/her dancing skill ai. At the beginning of the lesson they line up from left to right. While there is at least one couple of a boy and a girl in the line, the following process is repeated: the boy and girl who stand next to each other, having the minimal difference in dancing skills start to dance. If there are several such couples, the one first from the left starts to dance. After a couple leaves to dance, the line closes again, i.e. as a result the line is always continuous. The difference in dancing skills is understood as the absolute value of difference of ai variable. Your task is to find out what pairs and in what order will start dancing.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 2·105) — the number of people. The next line contains n symbols B or G without spaces. B stands for a boy, G stands for a girl. The third line contains n space-separated integers ai (1 ≤ ai ≤ 107) — the dancing skill. People are specified from left to right in the order in which they lined up.

## Output Format
Print the resulting number of couples k. Then print k lines containing two numerals each — the numbers of people forming the couple. The people are numbered with integers from 1 to n from left to right. When a couple leaves to dance you shouldn't renumber the people. The numbers in one couple should be sorted in the increasing order. Print the couples in the order in which they leave to dance.

## Examples
```input
4
BGBG
4 2 4 3
```
```output
2
3 4
1 2
```
-----
```input
4
BBGG
4 6 1 5
```
```output
2
2 3
1 4
```
-----
```input
4
BGBB
1 1 2 3
```
```output
1
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya is a born Berland film director, he is currently working on a new blockbuster, "The Unexpected". Vasya knows from his own experience how important it is to choose the main characters' names and surnames wisely. He made up a list of n names and n surnames that he wants to use. Vasya haven't decided yet how to call characters, so he is free to match any name to any surname. Now he has to make the list of all the main characters in the following format: "Name1 Surname1, Name2 Surname2, ..., Namen Surnamen", i.e. all the name-surname pairs should be separated by exactly one comma and exactly one space, and the name should be separated from the surname by exactly one space. First of all Vasya wants to maximize the number of the pairs, in which the name and the surname start from one letter. If there are several such variants, Vasya wants to get the lexicographically minimal one. Help him.

An answer will be verified a line in the format as is shown above, including the needed commas and spaces. It's the lexicographical minimality of such a line that needs to be ensured. The output line shouldn't end with a space or with a comma.

## Input Format
The first input line contains number n (1 ≤ n ≤ 100) — the number of names and surnames. Then follow n lines — the list of names. Then follow n lines — the list of surnames. No two from those 2n strings match. Every name and surname is a non-empty string consisting of no more than 10 Latin letters. It is guaranteed that the first letter is uppercase and the rest are lowercase.

## Output Format
The output data consist of a single line — the needed list. Note that one should follow closely the output data format!

## Examples
```input
4
Ann
Anna
Sabrina
John
Petrov
Ivanova
Stoltz
Abacaba
```
```output
Ann Abacaba, Anna Ivanova, John Petrov, Sabrina Stoltz
```
-----
```input
4
Aa
Ab
Ac
Ba
Ad
Ae
Bb
Bc
```
```output
Aa Ad, Ab Ae, Ac Bb, Ba Bc
```

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
Once Vasya needed to transport m goats and m wolves from riverbank to the other as quickly as possible. The boat can hold n animals and Vasya, in addition, he is permitted to put less than n animals in the boat. If in one place (on one of the banks or in the boat) the wolves happen to strictly outnumber the goats, then the wolves eat the goats and Vasya gets upset. When Vasya swims on the boat from one shore to the other, he must take at least one animal to accompany him, otherwise he will get bored and he will, yet again, feel upset. When the boat reaches the bank, first all the animals get off simultaneously, and then the animals chosen by Vasya simultaneously get on the boat. That means that at the moment when the animals that have just arrived have already got off and the animals that are going to leave haven't yet got on, somebody might eat someone. Vasya needs to transport all the animals from one river bank to the other so that nobody eats anyone and Vasya doesn't get upset. What is the minimal number of times he will have to cross the river?

## Input Format
The first line contains two space-separated numbers m and n (1 ≤ m, n ≤ 105) — the number of animals and the boat's capacity.

## Output Format
If it is impossible to transport all the animals so that no one got upset, and all the goats survived, print -1. Otherwise print the single number — how many times Vasya will have to cross the river.

## Examples
```input
3 2
```
```output
11
```
-----
```input
33 3
```
```output
-1
```

## Note
The first sample match to well-known problem for children.

Now solve the problem and return the code.