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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given n × m table. Each cell of the table is colored white or black. Find the number of non-empty sets of cells such that:

1. All cells in a set have the same color.
2. Every two cells in a set share row or column.

## Input Format
The first line of input contains integers n and m (1 ≤ n, m ≤ 50) — the number of rows and the number of columns correspondingly.

The next n lines of input contain descriptions of rows. There are m integers, separated by spaces, in each line. The number equals 0 if the corresponding cell is colored white and equals 1 if the corresponding cell is colored black.

## Output Format
Output single integer  — the number of non-empty sets from the problem description.

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

## Note
In the second example, there are six one-element sets. Additionally, there are two two-element sets, the first one consists of the first and the third cells of the first row, the second one consists of the first and the third cells of the second row. To sum up, there are 8 sets.

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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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.
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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
— This is not playing but duty as allies of justice, Nii-chan!

— Not allies but justice itself, Onii-chan!

With hands joined, go everywhere at a speed faster than our thoughts! This time, the Fire Sisters — Karen and Tsukihi — is heading for somewhere they've never reached — water-surrounded islands!

There are three clusters of islands, conveniently coloured red, blue and purple. The clusters consist of a, b and c distinct islands respectively.

Bridges have been built between some (possibly all or none) of the islands. A bridge bidirectionally connects two different islands and has length 1. For any two islands of the same colour, either they shouldn't be reached from each other through bridges, or the shortest distance between them is at least 3, apparently in order to prevent oddities from spreading quickly inside a cluster.

The Fire Sisters are ready for the unknown, but they'd also like to test your courage. And you're here to figure out the number of different ways to build all bridges under the constraints, and give the answer modulo 998 244 353. Two ways are considered different if a pair of islands exist, such that there's a bridge between them in one of them, but not in the other.

## Input Format
The first and only line of input contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 5 000) — the number of islands in the red, blue and purple clusters, respectively.

## Output Format
Output one line containing an integer — the number of different ways to build bridges, modulo 998 244 353.

## Examples
```input
1 1 1
```
```output
8
```
-----
```input
1 2 2
```
```output
63
```
-----
```input
1 3 5
```
```output
3264
```
-----
```input
6 2 9
```
```output
813023575
```

## Note
In the first example, there are 3 bridges that can possibly be built, and no setup of bridges violates the restrictions. Thus the answer is 23 = 8.

In the second example, the upper two structures in the figure below are instances of valid ones, while the lower two are invalid due to the blue and purple clusters, respectively.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Petya had a tree consisting of n vertices numbered with integers from 1 to n. Accidentally he lost his tree.

Petya remembers information about k vertices: distances from each of them to each of the n tree vertices.

Your task is to restore any tree that satisfies the information that Petya remembers or report that such tree doesn't exist.

## Input Format
The first line contains two integers n and k (2 ≤ n ≤ 30 000, 1 ≤ k ≤ min(200, n)) — the number of vertices in the tree and the number of vertices about which Petya remembers distance information.

The following k lines contain remembered information. The i-th line contains n integers di, 1, di, 2, ..., di, n (0 ≤ di, j ≤ n - 1), where di, j — the distance to j-th vertex from the i-th vertex that Petya remembers.

## Output Format
If there are no suitable trees, print -1.

In the other case, print n - 1 lines: each line should contain two vertices connected by edge in the required tree. You can print edges and vertices in an edge in any order. The tree vertices are enumerated from 1 to n.

If there are many solutions print any of them.

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

## Note
Picture for the first 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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 512.0 MB

# Problem
In a medieval kingdom, the economic crisis is raging. Milk drops fall, Economic indicators are deteriorating every day, money from the treasury disappear. To remedy the situation, King Charles Sunnyface decided make his n sons-princes marry the brides with as big dowry as possible.

In search of candidates, the king asked neighboring kingdoms, and after a while several delegations arrived with m unmarried princesses. Receiving guests, Karl learned that the dowry of the i th princess is wi of golden coins.

Although the action takes place in the Middle Ages, progressive ideas are widespread in society, according to which no one can force a princess to marry a prince whom she does not like. Therefore, each princess has an opportunity to choose two princes, for each of which she is ready to become a wife. The princes were less fortunate, they will obey the will of their father in the matter of choosing a bride.

Knowing the value of the dowry and the preferences of each princess, Charles wants to play weddings in such a way that the total dowry of the brides of all his sons would be as great as possible. At the same time to marry all the princes or princesses is not necessary. Each prince can marry no more than one princess, and vice versa, each princess can marry no more than one prince.

Help the king to organize the marriage of his sons in the most profitable way for the treasury.

## Input Format
The first line contains two integers n, m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000) — number of princes and princesses respectively.

Each of following m lines contains three integers ai, bi, wi (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 10 000) — number of princes, which i-th princess is ready to marry and the value of her dowry.

## Output Format
Print the only integer — the maximum number of gold coins that a king can get by playing the right weddings.

## Examples
```input
2 3
1 2 5
1 2 1
2 1 10
```
```output
15
```
-----
```input
3 2
1 2 10
3 2 20
```
```output
30
```

Now solve the problem and return the code.