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
Is it rated?

Here it is. The Ultimate Question of Competitive Programming, Codeforces, and Everything. And you are here to answer it.

Another Codeforces round has been conducted. No two participants have the same number of points. For each participant, from the top to the bottom of the standings, their rating before and after the round is known.

It's known that if at least one participant's rating has changed, then the round was rated for sure.

It's also known that if the round was rated and a participant with lower rating took a better place in the standings than a participant with higher rating, then at least one round participant's rating has changed.

In this problem, you should not make any other assumptions about the rating system.

Determine if the current round is rated, unrated, or it's impossible to determine whether it is rated of not.

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 1000) — the number of round participants.

Each of the next n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 4126) — the rating of the i-th participant before and after the round, respectively. The participants are listed in order from the top to the bottom of the standings.

## Output Format
If the round is rated for sure, print "rated". If the round is unrated for sure, print "unrated". If it's impossible to determine whether the round is rated or not, print "maybe".

## Examples
```input
6
3060 3060
2194 2194
2876 2903
2624 2624
3007 2991
2884 2884
```
```output
rated
```
-----
```input
4
1500 1500
1300 1300
1200 1200
1400 1400
```
```output
unrated
```
-----
```input
5
3123 3123
2777 2777
2246 2246
2246 2246
1699 1699
```
```output
maybe
```

## Note
In the first example, the ratings of the participants in the third and fifth places have changed, therefore, the round was rated.

In the second example, no one's rating has changed, but the participant in the second place has lower rating than the participant in the fourth place. Therefore, if the round was rated, someone's rating would've changed for sure.

In the third example, no one's rating has changed, and the participants took places in non-increasing order of their rating. Therefore, it's impossible to determine whether the round is rated or not.

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
Unlucky year in Berland is such a year that its number n can be represented as n = xa + yb, where a and b are non-negative integer numbers.

For example, if x = 2 and y = 3 then the years 4 and 17 are unlucky (4 = 20 + 31, 17 = 23 + 32 = 24 + 30) and year 18 isn't unlucky as there is no such representation for it.

Such interval of years that there are no unlucky years in it is called The Golden Age.

You should write a program which will find maximum length of The Golden Age which starts no earlier than the year l and ends no later than the year r. If all years in the interval [l, r] are unlucky then the answer is 0.

## Input Format
The first line contains four integer numbers x, y, l and r (2 ≤ x, y ≤ 1018, 1 ≤ l ≤ r ≤ 1018).

## Output Format
Print the maximum length of The Golden Age within the interval [l, r].

If all years in the interval [l, r] are unlucky then print 0.

## Examples
```input
2 3 1 10
```
```output
1
```
-----
```input
3 5 10 22
```
```output
8
```
-----
```input
2 3 3 5
```
```output
0
```

## Note
In the first example the unlucky years are 2, 3, 4, 5, 7, 9 and 10. So maximum length of The Golden Age is achived in the intervals [1, 1], [6, 6] and [8, 8].

In the second example the longest Golden Age is the interval [15, 22].

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
Holidays have finished. Thanks to the help of the hacker Leha, Noora managed to enter the university of her dreams which is located in a town Pavlopolis. It's well known that universities provide students with dormitory for the period of university studies. Consequently Noora had to leave Vičkopolis and move to Pavlopolis. Thus Leha was left completely alone in a quiet town Vičkopolis. He almost even fell into a depression from boredom!

Leha came up with a task for himself to relax a little. He chooses two integers A and B and then calculates the greatest common divisor of integers "A factorial" and "B factorial". Formally the hacker wants to find out GCD(A!, B!). It's well known that the factorial of an integer x is a product of all positive integers less than or equal to x. Thus x! = 1·2·3·...·(x - 1)·x. For example 4! = 1·2·3·4 = 24. Recall that GCD(x, y) is the largest positive integer q that divides (without a remainder) both x and y.

Leha has learned how to solve this task very effective. You are able to cope with it not worse, aren't you?

## Input Format
The first and single line contains two integers A and B (1 ≤ A, B ≤ 109, min(A, B) ≤ 12).

## Output Format
Print a single integer denoting the greatest common divisor of integers A! and B!.

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

## Note
Consider the sample.

4! = 1·2·3·4 = 24. 3! = 1·2·3 = 6. The greatest common divisor of integers 24 and 6 is exactly 6.

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
Erelong Leha was bored by calculating of the greatest common divisor of two factorials. Therefore he decided to solve some crosswords. It's well known that it is a very interesting occupation though it can be very difficult from time to time. In the course of solving one of the crosswords, Leha had to solve a simple task. You are able to do it too, aren't you?

Leha has two strings s and t. The hacker wants to change the string s at such way, that it can be found in t as a substring. All the changes should be the following: Leha chooses one position in the string s and replaces the symbol in this position with the question mark "?". The hacker is sure that the question mark in comparison can play the role of an arbitrary symbol. For example, if he gets string s="ab?b" as a result, it will appear in t="aabrbb" as a substring.

Guaranteed that the length of the string s doesn't exceed the length of the string t. Help the hacker to replace in s as few symbols as possible so that the result of the replacements can be found in t as a substring. The symbol "?" should be considered equal to any other symbol.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ m ≤ 1000) — the length of the string s and the length of the string t correspondingly.

The second line contains n lowercase English letters — string s.

The third line contains m lowercase English letters — string t.

## Output Format
In the first line print single integer k — the minimal number of symbols that need to be replaced.

In the second line print k distinct integers denoting the positions of symbols in the string s which need to be replaced. Print the positions in any order. If there are several solutions print any of them. The numbering of the positions begins from one.

## Examples
```input
3 5
abc
xaybz
```
```output
2
2 3
```
-----
```input
4 10
abcd
ebceabazcd
```
```output
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
For each positive integer n consider the integer ψ(n) which is obtained from n by replacing every digit a in the decimal notation of n with the digit (9  -  a). We say that ψ(n) is the reflection of n. For example, reflection of 192 equals 807. Note that leading zeros (if any) should be omitted. So reflection of 9 equals 0, reflection of 91 equals 8.

Let us call the weight of the number the product of the number and its reflection. Thus, the weight of the number 10 is equal to 10·89 = 890.

Your task is to find the maximum weight of the numbers in the given range [l, r] (boundaries are included).

## Input Format
Input contains two space-separated integers l and r (1 ≤ l ≤ r ≤ 109) — bounds of the range.

## Output Format
Output should contain single integer number: maximum value of the product n·ψ(n), where l ≤ n ≤ r.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout (also you may use %I64d).

## Examples
```input
3 7
```
```output
20
```
-----
```input
1 1
```
```output
8
```
-----
```input
8 10
```
```output
890
```

## Note
In the third sample weight of 8 equals 8·1 = 8, weight of 9 equals 9·0 = 0, weight of 10 equals 890.

Thus, maximum value of the product is equal to 890.

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
Physicist Woll likes to play one relaxing game in between his search of the theory of everything.

Game interface consists of a rectangular n × m playing field and a dashboard. Initially some cells of the playing field are filled while others are empty. Dashboard contains images of all various connected (we mean connectivity by side) figures of 2, 3, 4 and 5 cells, with all their rotations and reflections. Player can copy any figure from the dashboard and place it anywhere at the still empty cells of the playing field. Of course any figure can be used as many times as needed.

Woll's aim is to fill the whole field in such a way that there are no empty cells left, and also... just have some fun.

Every initially empty cell should be filled with exactly one cell of some figure. Every figure should be entirely inside the board.

In the picture black cells stand for initially filled cells of the field, and one-colour regions represent the figures.

## Input Format
First line contains integers n and m (1 ≤ n, m ≤ 1000) — the height and the width of the field correspondingly. Next n lines contain m symbols each. They represent the field in a natural way: j-th character of the i-th line is "#" if the corresponding cell is filled, and "." if it is empty.

## Output Format
If there is no chance to win the game output the only number "-1" (without the quotes). Otherwise output any filling of the field by the figures in the following format: each figure should be represented by some digit and figures that touch each other by side should be represented by distinct digits. Every initially filled cell should be represented by "#".

## Examples
```input
2 3
...
#.#
```
```output
000
#0#
```
-----
```input
3 3
.#.
...
..#
```
```output
5#1
511
55#
```
-----
```input
3 3
...
.##
.#.
```
```output
-1
```
-----
```input
1 2
##
```
```output
##
```

## Note
In the third sample, there is no way to fill a cell with no empty neighbours.

In the forth sample, Woll does not have to fill anything, so we should output the field from the input.

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
"Multidimensional spaces are completely out of style these days, unlike genetics problems" — thought physicist Woll and changed his subject of study to bioinformatics. Analysing results of sequencing he faced the following problem concerning DNA sequences. We will further think of a DNA sequence as an arbitrary string of uppercase letters "A", "C", "G" and "T" (of course, this is a simplified interpretation).

Let w be a long DNA sequence and s1, s2, ..., sm — collection of short DNA sequences. Let us say that the collection filters w iff w can be covered with the sequences from the collection. Certainly, substrings corresponding to the different positions of the string may intersect or even cover each other. More formally: denote by |w| the length of w, let symbols of w be numbered from 1 to |w|. Then for each position i in w there exist pair of indices l, r (1 ≤ l ≤ i ≤ r ≤ |w|) such that the substring w[l ... r] equals one of the elements s1, s2, ..., sm of the collection.

Woll wants to calculate the number of DNA sequences of a given length filtered by a given collection, but he doesn't know how to deal with it. Help him! Your task is to find the number of different DNA sequences of length n filtered by the collection {si}.

Answer may appear very large, so output it modulo 1000000009.

## Input Format
First line contains two integer numbers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10) — the length of the string and the number of sequences in the collection correspondently.

Next m lines contain the collection sequences si, one per line. Each si is a nonempty string of length not greater than 10. All the strings consist of uppercase letters "A", "C", "G", "T". The collection may contain identical strings.

## Output Format
Output should contain a single integer — the number of strings filtered by the collection modulo 1000000009 (109 + 9).

## Examples
```input
2 1
A
```
```output
1
```
-----
```input
6 2
CAT
TACT
```
```output
2
```

## Note
In the first sample, a string has to be filtered by "A". Clearly, there is only one such string: "AA".

In the second sample, there exist exactly two different strings satisfying the condition (see the pictures below).

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A sequence a0, a1, ... is called a recurrent binary sequence, if each term ai (i = 0, 1, ...) is equal to 0 or 1 and there exist coefficients $$c_1, c_2, \ldots, c_k \in \{0, 1\}$$ such that

an = c1·an - 1 + c2·an - 2 + ... + ck·an - k (mod 2),

Note that such a sequence can be uniquely recovered from any k-tuple {as, as + 1, ..., as + k - 1} and so it is periodic. Moreover, if a k-tuple contains only zeros, then the sequence contains only zeros, so this case is not very interesting. Otherwise the minimal period of the sequence is not greater than 2k - 1, as k-tuple determines next element, and there are 2k - 1 non-zero k-tuples. Let us call a sequence long if its minimal period is exactly 2k - 1. Your task is to find a long sequence for a given k, if there is any.

## Input Format
Input contains a single integer k (2 ≤ k ≤ 50).

## Output Format
If there is no long sequence for a given k, output "-1" (without quotes). Otherwise the first line of the output should contain k integer numbers: c1, c2, ..., ck (coefficients). The second line should contain first k elements of the sequence: a0, a1, ..., ak - 1. All of them (elements and coefficients) should be equal to 0 or 1, and at least one ci has to be equal to 1.

If there are several solutions, output any.

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

## Note
1. In the first sample: c1 = 1, c2 = 1, so an = an - 1 + an - 2  (mod 2). Thus the sequence will be:

so its period equals 3 = 22 - 1.

2. In the second sample: c1 = 0, c2 = 1, c3 = 1, so an = an - 2 + an - 3  (mod 2). Thus our sequence is:

and its period equals 7 = 23 - 1.

Periods are colored.

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
Rock... Paper!

After Karen have found the deterministic winning (losing?) strategy for rock-paper-scissors, her brother, Koyomi, comes up with a new game as a substitute. The game works as follows.

A positive integer n is decided first. Both Koyomi and Karen independently choose n distinct positive integers, denoted by x1, x2, ..., xn and y1, y2, ..., yn respectively. They reveal their sequences, and repeat until all of 2n integers become distinct, which is the only final state to be kept and considered.

Then they count the number of ordered pairs (i, j) (1 ≤ i, j ≤ n) such that the value xi xor yj equals to one of the 2n integers. Here xor means the bitwise exclusive or operation on two integers, and is denoted by operators ^ and/or xor in most programming languages.

Karen claims a win if the number of such pairs is even, and Koyomi does otherwise. And you're here to help determine the winner of their latest game.

## Input Format
The first line of input contains a positive integer n (1 ≤ n ≤ 2 000) — the length of both sequences.

The second line contains n space-separated integers x1, x2, ..., xn (1 ≤ xi ≤ 2·106) — the integers finally chosen by Koyomi.

The third line contains n space-separated integers y1, y2, ..., yn (1 ≤ yi ≤ 2·106) — the integers finally chosen by Karen.

Input guarantees that the given 2n integers are pairwise distinct, that is, no pair (i, j) (1 ≤ i, j ≤ n) exists such that one of the following holds: xi = yj; i ≠ j and xi = xj; i ≠ j and yi = yj.

## Output Format
Output one line — the name of the winner, that is, "Koyomi" or "Karen" (without quotes). Please be aware of the capitalization.

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

## Note
In the first example, there are 6 pairs satisfying the constraint: (1, 1), (1, 2), (2, 1), (2, 3), (3, 2) and (3, 3). Thus, Karen wins since 6 is an even number.

In the second example, there are 16 such pairs, and Karen wins again.

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
Even if the world is full of counterfeits, I still regard it as wonderful.

Pile up herbs and incense, and arise again from the flames and ashes of its predecessor — as is known to many, the phoenix does it like this.

The phoenix has a rather long lifespan, and reincarnates itself once every a! years. Here a! denotes the factorial of integer a, that is, a! = 1 × 2 × ... × a. Specifically, 0! = 1.

Koyomi doesn't care much about this, but before he gets into another mess with oddities, he is interested in the number of times the phoenix will reincarnate in a timespan of b! years, that is, $$\frac{6!}{a!}$$. Note that when b ≥ a this value is always integer.

As the answer can be quite large, it would be enough for Koyomi just to know the last digit of the answer in decimal representation. And you're here to provide Koyomi with this knowledge.

## Input Format
The first and only line of input contains two space-separated integers a and b (0 ≤ a ≤ b ≤ 1018).

## Output Format
Output one line containing a single decimal digit — the last digit of the value that interests Koyomi.

## Examples
```input
2 4
```
```output
2
```
-----
```input
0 10
```
```output
0
```
-----
```input
107 109
```
```output
2
```

## Note
In the first example, the last digit of $$\frac{4!}{2!} = 12$$ is 2;

In the second example, the last digit of $$\frac{10!}{0!} = 3628800$$ is 0;

In the third example, the last digit of $$\frac{109!}{107!} = 11772$$ is 2.

Now solve the problem and return the code.