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
Furik loves painting stars. A star is a shape that results if we take a regular pentagon and paint all diagonals in it.

Recently he decided to teach Rubik to paint stars. After many years of training Rubik could paint stars easily. But now Furik decided to test Rubik and complicated the task. Rubik must paint n stars, observing the following rules:

- all stars must be painted in a single move (i.e. it is forbidden to take the pen away from the paper);
- it is forbidden to paint the same segment of non-zero length more than once;
- the stars can intersect only in their vertexes;
- the length of a side of the regular pentagon, in which Rubik paints each star, must equal 10.

Help Rubik to cope with this hard task.

## Input Format
A single line contains an integer (1 ≤ n ≤ 100) — the number of stars to paint.

## Output Format
On the first line print an integer m (1 ≤ m ≤ 5·n). On the next m lines print coordinates of m distinct points with accuracy of at least 9 and at most 100 digits after decimal point. All coordinates should not exceed 5000 in their absolute value. On each of the next n lines print 5 integers — the indexes of the points that form the given star in the clockwise or counterclockwise order. On the next line print 5·n + 1 integers — the numbers of points in the order, in which Rubik paints stars. That is, if number with index i is ai, and number with index i + 1 is ai + 1, then points with indexes ai and ai + 1 will have a segment painted between them.

You can consider all m printed points indexed from 1 to m in the order, in which they occur in the output. Separate the numbers on the lines with whitespaces.

Note that the answer has an imprecise validation. Try to obtain as accurate a solution as possible. The validator performs all calculations considering that the absolute error of a participant's answer is not more than 10 - 8.

## Examples
```input
1
```
```output
5
3.830127018922193 3.366025403784439
-3.601321235851749 10.057331467373021
0.466045194906253 19.192786043799030
10.411264148588986 18.147501411122495
12.490381056766580 8.366025403784439
1 2 3 4 5
1 3 5 2 4 1
```

## Note
The initial position of points in the sample is:

The order in which Rubik can paint segments is:

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
Rubik is very keen on number permutations.

A permutation a with length n is a sequence, consisting of n different numbers from 1 to n. Element number i (1 ≤ i ≤ n) of this permutation will be denoted as ai.

Furik decided to make a present to Rubik and came up with a new problem on permutations. Furik tells Rubik two number permutations: permutation a with length n and permutation b with length m. Rubik must give an answer to the problem: how many distinct integers d exist, such that sequence c (c1 = a1 + d, c2 = a2 + d, ..., cn = an + d) of length n is a subsequence of b.

Sequence a is a subsequence of sequence b, if there are such indices i1, i2, ..., in (1 ≤ i1 < i2 < ... < in ≤ m), that a1 = bi1, a2 = bi2, ..., an = bin, where n is the length of sequence a, and m is the length of sequence b.

You are given permutations a and b, help Rubik solve the given problem.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ m ≤ 200000) — the sizes of the given permutations. The second line contains n distinct integers — permutation a, the third line contains m distinct integers — permutation b. Numbers on the lines are separated by spaces.

## Output Format
On a single line print the answer to the problem.

## Examples
```input
1 1
1
1
```
```output
1
```
-----
```input
1 2
1
2 1
```
```output
2
```
-----
```input
3 3
2 3 1
1 2 3
```
```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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
One day shooshuns found a sequence of n integers, written on a blackboard. The shooshuns can perform one operation with it, the operation consists of two steps:

1. Find the number that goes k-th in the current sequence and add the same number to the end of the sequence;
2. Delete the first number of the current sequence.

The shooshuns wonder after how many operations all numbers on the board will be the same and whether all numbers will ever be the same.

## Input Format
The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 105).

The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 105) — the sequence that the shooshuns found.

## Output Format
Print the minimum number of operations, required for all numbers on the blackboard to become the same. If it is impossible to achieve, print -1.

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

## Note
In the first test case after the first operation the blackboard will have sequence [1, 1, 1]. So, one operation is enough to make all numbers the same. Thus, the answer equals one.

In the second test case the sequence will never consist of the same numbers. It will always contain at least two distinct numbers 3 and 1. Thus, the answer equals -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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
The Free Meteor Association (FMA) has got a problem: as meteors are moving, the Universal Cosmic Descriptive Humorous Program (UCDHP) needs to add a special module that would analyze this movement.

UCDHP stores some secret information about meteors as an n × m table with integers in its cells. The order of meteors in the Universe is changing. That's why the main UCDHP module receives the following queries:

- The query to swap two table rows;
- The query to swap two table columns;
- The query to obtain a secret number in a particular table cell.

As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you.

## Input Format
The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 500000) — the number of table columns and rows and the number of queries, correspondingly.

Next n lines contain m space-separated numbers each — the initial state of the table. Each number p in the table is an integer and satisfies the inequality 0 ≤ p ≤ 106.

Next k lines contain queries in the format "si xi yi", where si is one of the characters "с", "r" or "g", and xi, yi are two integers.

- If si = "c", then the current query is the query to swap columns with indexes xi and yi (1 ≤ x, y ≤ m, x ≠ y);
- If si = "r", then the current query is the query to swap rows with indexes xi and yi (1 ≤ x, y ≤ n, x ≠ y);
- If si = "g", then the current query is the query to obtain the number that located in the xi-th row and in the yi-th column (1 ≤ x ≤ n, 1 ≤ y ≤ m).

The table rows are considered to be indexed from top to bottom from 1 to n, and the table columns — from left to right from 1 to m.

## Output Format
For each query to obtain a number (si = "g") print the required number. Print the answers to the queries in the order of the queries in the input.

## Examples
```input
3 3 5
1 2 3
4 5 6
7 8 9
g 3 2
r 3 2
c 2 3
g 2 2
g 3 2
```
```output
8
9
6
```
-----
```input
2 3 3
1 2 4
3 1 5
c 2 1
r 1 2
g 1 3
```
```output
5
```

## Note
Let's see how the table changes in the second test case.

After the first operation is fulfilled, the table looks like that:

2 1 4

1 3 5

After the second operation is fulfilled, the table looks like that:

1 3 5

2 1 4

So the answer to the third query (the number located in the first row and in the third column) will be 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
To confuse the opponents, the Galactic Empire represents fractions in an unusual format. The fractions are represented as two sets of integers. The product of numbers from the first set gives the fraction numerator, the product of numbers from the second set gives the fraction denominator. However, it turned out that the programs that work with fractions in this representations aren't complete, they lack supporting the operation of reducing fractions. Implement this operation and the Empire won't forget you.

## Input Format
The first input line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) that show how many numbers the first set (the numerator) and the second set (the denominator) contain, correspondingly.

The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 107) — the numbers that are multiplied to produce the numerator.

The third line contains m space-separated integers: b1, b2, ..., bm (1 ≤ bi ≤ 107) — the numbers that are multiplied to produce the denominator.

## Output Format
Print the answer to the problem in the form, similar to the form of the input data. The number of values in the sets you print nout, mout must satisfy the inequality 1 ≤ nout, mout ≤ 105, and the actual values in the sets aout, i and bout, i must satisfy the inequality 1 ≤ aout, i, bout, i ≤ 107.

Separate the values in the lines by spaces. The printed fraction must be reduced, that is, there mustn't be such integer x (x > 1), that the numerator and the denominator of the printed fraction are divisible by x. If there are several matching answers, print any of them.

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

## Note
In the first test sample the numerator equals 1000, the denominator equals 500. If we reduce fraction 1000/500 by the greatest common divisor of the numerator and the denominator (by 500), we obtain fraction 2/1.

In the second test sample the numerator equals 2000, the denominator equals 300. If we reduce fraction 2000/300 by the greatest common divisor of the numerator and the denominator (by 100), we obtain fraction 20/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
Recently a top secret mission to Mars has taken place. As a result, scientists managed to obtain some information about the Martian DNA. Now we know that any Martian DNA contains at most m different nucleotides, numbered from 1 to m. Special characteristics of the Martian DNA prevent some nucleotide pairs from following consecutively in this chain. For example, if the nucleotide 1 and nucleotide 2 can not follow consecutively in the Martian DNA, then the chain of nucleotides [1, 2] is not a valid chain of Martian DNA, but the chain of nucleotides [2, 1] can be a valid chain (if there is no corresponding restriction). The number of nucleotide pairs that can't follow in the DNA chain consecutively, is k.

The needs of gene research required information about the quantity of correct n-long chains of the Martian DNA. Your task is to write a program that will calculate this value.

## Input Format
The first line contains three space-separated integers n, m, k (1 ≤ n ≤ 1015, 1 ≤ m ≤ 52, 0 ≤ k ≤ m2).

Next k lines contain two characters each, without a space between them, representing a forbidden nucleotide pair. The first character represents the first nucleotide in the forbidden pair, the second character represents the second nucleotide.

The nucleotides with assigned numbers from 1 to 26 are represented by English alphabet letters from "a" to "z" (1 is an "a", 2 is a "b", ..., 26 is a "z"). Nucleotides with assigned numbers from 27 to 52 are represented by English alphabet letters from "A" to "Z" (27 is an "A", 28 is a "B", ..., 52 is a "Z").

It is guaranteed that each forbidden pair occurs at most once in the input. It is guaranteed that nucleotide's numbers in all forbidden pairs cannot be more than m. Note that order is important in nucleotide pairs.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

## Output Format
Print a single integer — the sought number modulo 1000000007 (109 + 7).

## Examples
```input
3 3 2
ab
ba
```
```output
17
```
-----
```input
3 3 0
```
```output
27
```
-----
```input
2 1 1
aa
```
```output
0
```

## Note
In the second test case all possible three-nucleotide DNAs are permitted. Each nucleotide can take one of three values, thus in total there are 27 distinct three nucleotide DNAs.

In the third test sample we cannot make any DNA of two nucleotides — the only possible nucleotide "a" cannot occur two times consecutively.

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're given a string of lower-case Latin letters. Your task is to find the length of its longest substring that can be met in the string at least twice. These occurrences can overlap (see sample test 2).

## Input Format
The first input line contains the string. It's guaranteed, that the string is non-empty, consists of lower-case Latin letters, and its length doesn't exceed 100.

## Output Format
Output one number — length of the longest substring that can be met in the string at least twice.

## Examples
```input
abcd
```
```output
0
```
-----
```input
ababa
```
```output
3
```
-----
```input
zzz
```
```output
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
Recently Bob invented a new game with a tree (we should remind you, that a tree is a connected graph without cycles): he deletes any (possibly, zero) amount of edges of the tree, and counts the product of sizes of the connected components left after the deletion. Your task is to find out the maximum number that Bob can get in his new game for a given tree.

## Input Format
The first input line contains integer number n (1 ≤ n ≤ 700) — amount of vertices in the tree. The following n - 1 lines contain the description of the edges. Each line contains the pair of vertices' indexes, joined by an edge, ai, bi (1 ≤ ai, bi ≤ n). It's guaranteed that the graph described in the input is a tree.

## Output Format
Output the only number — the maximum product of sizes of the connected components, that Bob can get after deleting some of the tree's edges.

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

# Problem
Those days, many boys use beautiful girls' photos as avatars in forums. So it is pretty hard to tell the gender of a user at the first glance. Last year, our hero went to a forum and had a nice chat with a beauty (he thought so). After that they talked very often and eventually they became a couple in the network.

But yesterday, he came to see "her" in the real world and found out "she" is actually a very strong man! Our hero is very sad and he is too tired to love again now. So he came up with a way to recognize users' genders by their user names.

This is his method: if the number of distinct characters in one's user name is odd, then he is a male, otherwise she is a female. You are given the string that denotes the user name, please help our hero to determine the gender of this user by his method.

## Input Format
The first line contains a non-empty string, that contains only lowercase English letters — the user name. This string contains at most 100 letters.

## Output Format
If it is a female by our hero's method, print "CHAT WITH HER!" (without the quotes), otherwise, print "IGNORE HIM!" (without the quotes).

## Examples
```input
wjmzbmr
```
```output
CHAT WITH HER!
```
-----
```input
xiaodao
```
```output
IGNORE HIM!
```
-----
```input
sevenkplus
```
```output
CHAT WITH HER!
```

## Note
For the first example. There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So wjmzbmr is a female and you should print "CHAT WITH HER!".

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
Let's denote d(n) as the number of divisors of a positive integer n. You are given three integers a, b and c. Your task is to calculate the following sum:

$$\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}d(i \cdot j \cdot k)$$

Find the sum modulo 1073741824 (230).

## Input Format
The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 100).

## Output Format
Print a single integer — the required sum modulo 1073741824 (230).

## Examples
```input
2 2 2
```
```output
20
```
-----
```input
5 6 7
```
```output
1520
```

## Note
For the first example.

- d(1·1·1) = d(1) = 1;
- d(1·1·2) = d(2) = 2;
- d(1·2·1) = d(2) = 2;
- d(1·2·2) = d(4) = 3;
- d(2·1·1) = d(2) = 2;
- d(2·1·2) = d(4) = 3;
- d(2·2·1) = d(4) = 3;
- d(2·2·2) = d(8) = 4.

So the result is 1 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 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 sequence of colorful stones. The color of each stone is one of red, green, or blue. You are given a string s. The i-th (1-based) character of s represents the color of the i-th stone. If the character is "R", "G", or "B", the color of the corresponding stone is red, green, or blue, respectively.

Initially Squirrel Liss is standing on the first stone. You perform instructions one or more times.

Each instruction is one of the three types: "RED", "GREEN", or "BLUE". After an instruction c, if Liss is standing on a stone whose colors is c, Liss will move one stone forward, else she will not move.

You are given a string t. The number of instructions is equal to the length of t, and the i-th character of t represents the i-th instruction.

Calculate the final position of Liss (the number of the stone she is going to stand on in the end) after performing all the instructions, and print its 1-based position. It is guaranteed that Liss don't move out of the sequence.

## Input Format
The input contains two lines. The first line contains the string s (1 ≤ |s| ≤ 50). The second line contains the string t (1 ≤ |t| ≤ 50). The characters of each string will be one of "R", "G", or "B". It is guaranteed that Liss don't move out of the sequence.

## Output Format
Print the final 1-based position of Liss in a single line.

## Examples
```input
RGB
RRR
```
```output
2
```
-----
```input
RRRBGBRBBB
BBBRR
```
```output
3
```
-----
```input
BRRBGBRGRBGRGRRGGBGBGBRGBRGRGGGRBRRRBRBBBGRRRGGBBB
BBRBGGRGRGBBBRBGRBRBBBBRBRRRBGBBGBBRRBBGGRBRRBRGRB
```
```output
15
```

Now solve the problem and return the code.