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
Fox Ciel is playing a game with numbers now.

Ciel has n positive integers: x1, x2, ..., xn. She can do the following operation as many times as needed: select two different indexes i and j such that xi > xj hold, and then apply assignment xi = xi - xj. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

## Input Format
The first line contains an integer n (2 ≤ n ≤ 100). Then the second line contains n integers: x1, x2, ..., xn (1 ≤ xi ≤ 100).

## Output Format
Output a single integer — the required minimal sum.

## Examples
```input
2
1 2
```
```output
2
```
-----
```input
3
2 4 6
```
```output
6
```
-----
```input
2
12 18
```
```output
12
```
-----
```input
5
45 12 27 30 18
```
```output
15
```

## Note
In the first example the optimal way is to do the assignment: x2 = x2 - x1.

In the second example the optimal sequence of operations is: x3 = x3 - x2, x2 = x2 - x1.

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
Fox Ciel has a board with n rows and n columns. So, the board consists of n × n cells. Each cell contains either a symbol '.', or a symbol '#'.

A cross on the board is a connected set of exactly five cells of the board that looks like a cross. The picture below shows how it looks.

Ciel wants to draw several (may be zero) crosses on the board. Each cross must cover exactly five cells with symbols '#', and any cell with symbol '#' must belong to some cross. No two crosses can share a cell.

Please, tell Ciel if she can draw the crosses in the described way.

## Input Format
The first line contains an integer n (3 ≤ n ≤ 100) — the size of the board.

Each of the next n lines describes one row of the board. The i-th line describes the i-th row of the board and consists of n characters. Each character is either a symbol '.', or a symbol '#'.

## Output Format
Output a single line with "YES" if Ciel can draw the crosses in the described way. Otherwise output a single line with "NO".

## Examples
```input
5
.#...
####.
.####
...#.
.....
```
```output
YES
```
-----
```input
4
####
####
####
####
```
```output
NO
```
-----
```input
6
.#....
####..
.####.
.#.##.
######
.#..#.
```
```output
YES
```
-----
```input
6
.#..#.
######
.####.
.####.
######
.#..#.
```
```output
NO
```
-----
```input
3
...
...
...
```
```output
YES
```

## Note
In example 1, you can draw two crosses. The picture below shows what they look like.

In example 2, the board contains 16 cells with '#', but each cross contains 5. Since 16 is not a multiple of 5, so it's impossible to cover all.

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
Teacher thinks that we make a lot of progress. Now we are even allowed to use decimal notation instead of counting sticks. After the test the teacher promised to show us a "very beautiful number". But the problem is, he's left his paper with the number in the teachers' office.

The teacher remembers that the "very beautiful number" was strictly positive, didn't contain any leading zeroes, had the length of exactly p decimal digits, and if we move the last digit of the number to the beginning, it grows exactly x times. Besides, the teacher is sure that among all such numbers the "very beautiful number" is minimal possible.

The teachers' office isn't near and the teacher isn't young. But we've passed the test and we deserved the right to see the "very beautiful number". Help to restore the justice, find the "very beautiful number" for us!

## Input Format
The single line contains integers p, x (1 ≤ p ≤ 106, 1 ≤ x ≤ 9).

## Output Format
If the teacher's made a mistake and such number doesn't exist, then print on a single line "Impossible" (without the quotes). Otherwise, print the "very beautiful number" without leading zeroes.

## Examples
```input
6 5
```
```output
142857
```
-----
```input
1 2
```
```output
Impossible
```
-----
```input
6 4
```
```output
102564
```

## Note
Sample 1: 142857·5 = 714285.

Sample 2: The number that consists of a single digit cannot stay what it is when multiplied by 2, thus, the answer to the test sample is "Impossible".

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
During the break, we decided to relax and play dominoes. Our box with Domino was empty, so we decided to borrow the teacher's dominoes.

The teacher responded instantly at our request. He put nm dominoes on the table as an n × 2m rectangle so that each of the n rows contained m dominoes arranged horizontally. Each half of each domino contained number (0 or 1).

We were taken aback, and the teacher smiled and said: "Consider some arrangement of dominoes in an n × 2m matrix. Let's count for each column of the matrix the sum of numbers in this column. Then among all such sums find the maximum one. Can you rearrange the dominoes in the matrix in such a way that the maximum sum will be minimum possible? Note that it is prohibited to change the orientation of the dominoes, they all need to stay horizontal, nevertheless dominoes are allowed to rotate by 180 degrees. As a reward I will give you all my dominoes".

We got even more taken aback. And while we are wondering what was going on, help us make an optimal matrix of dominoes.

## Input Format
The first line contains integers n, m (1 ≤ n, m ≤ 103).

In the next lines there is a description of the teachers' matrix. Each of next n lines contains m dominoes. The description of one domino is two integers (0 or 1), written without a space — the digits on the left and right half of the domino.

## Output Format
Print the resulting matrix of dominoes in the format: n lines, each of them contains m space-separated dominoes.

If there are multiple optimal solutions, print any of them.

## Examples
```input
2 3
01 11 00
00 01 11
```
```output
11 11 10
00 00 01
```
-----
```input
4 1
11
10
01
00
```
```output
11
10
01
00
```

## Note
Consider the answer for the first sample. There, the maximum sum among all columns equals 1 (the number of columns is 6, and not 3). Obviously, this maximum can't be less than 1, then such matrix is optimal.

Note that the dominoes can be rotated by 180 degrees.

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
Inna and Dima decided to surprise Sereja. They brought a really huge candy matrix, it's big even for Sereja! Let's number the rows of the giant matrix from 1 to n from top to bottom and the columns — from 1 to m, from left to right. We'll represent the cell on the intersection of the i-th row and j-th column as (i, j). Just as is expected, some cells of the giant candy matrix contain candies. Overall the matrix has p candies: the k-th candy is at cell (xk, yk).

The time moved closer to dinner and Inna was already going to eat p of her favourite sweets from the matrix, when suddenly Sereja (for the reason he didn't share with anyone) rotated the matrix x times clockwise by 90 degrees. Then he performed the horizontal rotate of the matrix y times. And then he rotated the matrix z times counterclockwise by 90 degrees. The figure below shows how the rotates of the matrix looks like.

Inna got really upset, but Duma suddenly understood two things: the candies didn't get damaged and he remembered which cells contained Inna's favourite sweets before Sereja's strange actions. Help guys to find the new coordinates in the candy matrix after the transformation Sereja made!

## Input Format
The first line of the input contains fix integers n, m, x, y, z, p (1 ≤ n, m ≤ 109; 0 ≤ x, y, z ≤ 109; 1 ≤ p ≤ 105).

Each of the following p lines contains two integers xk, yk (1 ≤ xk ≤ n; 1 ≤ yk ≤ m) — the initial coordinates of the k-th candy. Two candies can lie on the same cell.

## Output Format
For each of the p candies, print on a single line its space-separated new coordinates.

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

## Note
Just for clarity. Horizontal rotating is like a mirroring of the matrix. For matrix:

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
Dima took up the biology of bacteria, as a result of his experiments, he invented k types of bacteria. Overall, there are n bacteria at his laboratory right now, and the number of bacteria of type i equals ci. For convenience, we will assume that all the bacteria are numbered from 1 to n. The bacteria of type ci are numbered from $$(\sum_{k=1}^{i-1} c_k) + 1$$ to $$\sum_{k=1}^{i} c_k$$.

With the help of special equipment Dima can move energy from some bacteria into some other one. Of course, the use of such equipment is not free. Dima knows m ways to move energy from some bacteria to another one. The way with number i can be described with integers ui, vi and xi mean that this way allows moving energy from bacteria with number ui to bacteria with number vi or vice versa for xi dollars.

Dima's Chef (Inna) calls the type-distribution correct if there is a way (may be non-direct) to move energy from any bacteria of the particular type to any other bacteria of the same type (between any two bacteria of the same type) for zero cost.

As for correct type-distribution the cost of moving the energy depends only on the types of bacteria help Inna to determine is the type-distribution correct? If it is, print the matrix d with size k × k. Cell d[i][j] of this matrix must be equal to the minimal possible cost of energy-moving from bacteria with type i to bacteria with type j.

## Input Format
The first line contains three integers n, m, k (1 ≤ n ≤ 105; 0 ≤ m ≤ 105; 1 ≤ k ≤ 500). The next line contains k integers c1, c2, ..., ck (1 ≤ ci ≤ n). Each of the next m lines contains three integers ui, vi, xi (1 ≤ ui, vi ≤ 105; 0 ≤ xi ≤ 104). It is guaranteed that $$\sum_{i=1}^{k} c_i = n$$.

## Output Format
If Dima's type-distribution is correct, print string «Yes», and then k lines: in the i-th line print integers d[i][1], d[i][2], ..., d[i][k] (d[i][i] = 0). If there is no way to move energy from bacteria i to bacteria j appropriate d[i][j] must equal to -1. If the type-distribution isn't correct print «No».

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
The Finals of the "Russian Code Cup" 2214 will be held in n hotels. Two hotels (let's assume that they are the main hotels), will host all sorts of events, and the remaining hotels will accommodate the participants. The hotels are connected by n - 1 roads, you can get from any hotel to any other one.

The organizers wonder what is the minimum time all the participants need to get to the main hotels, if each participant goes to the main hotel that is nearest to him and moving between two hotels connected by a road takes one unit of time.

The hosts consider various options for the location of the main hotels. For each option help the organizers to find minimal time.

## Input Format
The first line contains an integer n (2 ≤ n ≤ 100000) — the number of hotels. The next n - 1 lines contain two integers each  — the numbers of the hotels that have a road between them. Consider hotels are numbered from 1 to n.

The next line contains an integer m (1 ≤ m ≤ 100000) — the number of queries. The following m lines contains two distinct integers each — the numbers of the hotels we assume to be the main.

## Output Format
For each request of the organizers print a single integer — the time that all participants need to reach the main hotels.

## Examples
```input
3
2 3
3 1
3
2 1
2 3
3 1
```
```output
1
1
1
```
-----
```input
4
1 4
1 2
2 3
3
1 4
1 3
2 3
```
```output
2
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 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
Iahub and Sorin are the best competitive programmers in their town. However, they can't both qualify to an important contest. The selection will be made with the help of a single problem. Blatnatalag, a friend of Iahub, managed to get hold of the problem before the contest. Because he wants to make sure Iahub will be the one qualified, he tells Iahub the following task.

You're given an (1-based) array a with n elements. Let's define function f(i, j) (1 ≤ i, j ≤ n) as (i - j)2 + g(i, j)2. Function g is calculated by the following pseudo-code:

Find a value mini ≠ j  f(i, j).

Probably by now Iahub already figured out the solution to this problem. Can you?

## Input Format
The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 104 ≤ a[i] ≤ 104).

## Output Format
Output a single integer — the value of mini ≠ j  f(i, j).

## Examples
```input
4
1 0 0 -1
```
```output
1
```
-----
```input
2
1 -1
```
```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 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
Many students live in a dormitory. A dormitory is a whole new world of funny amusements and possibilities but it does have its drawbacks.

There is only one shower and there are multiple students who wish to have a shower in the morning. That's why every morning there is a line of five people in front of the dormitory shower door. As soon as the shower opens, the first person from the line enters the shower. After a while the first person leaves the shower and the next person enters the shower. The process continues until everybody in the line has a shower.

Having a shower takes some time, so the students in the line talk as they wait. At each moment of time the students talk in pairs: the (2i - 1)-th man in the line (for the current moment) talks with the (2i)-th one.

Let's look at this process in more detail. Let's number the people from 1 to 5. Let's assume that the line initially looks as 23154 (person number 2 stands at the beginning of the line). Then, before the shower opens, 2 talks with 3, 1 talks with 5, 4 doesn't talk with anyone. Then 2 enters the shower. While 2 has a shower, 3 and 1 talk, 5 and 4 talk too. Then, 3 enters the shower. While 3 has a shower, 1 and 5 talk, 4 doesn't talk to anyone. Then 1 enters the shower and while he is there, 5 and 4 talk. Then 5 enters the shower, and then 4 enters the shower.

We know that if students i and j talk, then the i-th student's happiness increases by gij and the j-th student's happiness increases by gji. Your task is to find such initial order of students in the line that the total happiness of all students will be maximum in the end. Please note that some pair of students may have a talk several times. In the example above students 1 and 5 talk while they wait for the shower to open and while 3 has a shower.

## Input Format
The input consists of five lines, each line contains five space-separated integers: the j-th number in the i-th line shows gij (0 ≤ gij ≤ 105). It is guaranteed that gii = 0 for all i.

Assume that the students are numbered from 1 to 5.

## Output Format
Print a single integer — the maximum possible total happiness of the students.

## Examples
```input
0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0
```
```output
32
```
-----
```input
0 43 21 18 2
3 0 21 11 65
5 2 0 1 4
54 62 12 0 99
87 64 81 33 0
```
```output
620
```

## Note
In the first sample, the optimal arrangement of the line is 23154. In this case, the total happiness equals:

(g23 + g32 + g15 + g51) + (g13 + g31 + g54 + g45) + (g15 + g51) + (g54 + g45) = 32

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
Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a k-tree.

A k-tree is an infinite rooted tree where:

- each vertex has exactly k children;
- each edge has some weight;
- if we look at the edges that goes from some vertex to its children (exactly k edges), then their weights will equal 1, 2, 3, ..., k.

The picture below shows a part of a 3-tree.

Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (109 + 7).

## Input Format
A single line contains three space-separated integers: n, k and d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).

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

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

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
One day, after a difficult lecture a diligent student Sasha saw a graffitied desk in the classroom. She came closer and read: "Find such positive integer n, that among numbers n + 1, n + 2, ..., 2·n there are exactly m numbers which binary representation contains exactly k digits one".

The girl got interested in the task and she asked you to help her solve it. Sasha knows that you are afraid of large numbers, so she guaranteed that there is an answer that doesn't exceed 1018.

## Input Format
The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1018; 1 ≤ k ≤ 64).

## Output Format
Print the required number n (1 ≤ n ≤ 1018). If there are multiple answers, print any of them.

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

Now solve the problem and return the code.