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
Ivan is collecting coins. There are only $$$N$$$ different collectible coins, Ivan has $$$K$$$ of them. He will be celebrating his birthday soon, so all his $$$M$$$ freinds decided to gift him coins. They all agreed to three terms:

- Everyone must gift as many coins as others.
- All coins given to Ivan must be different.
- Not less than $$$L$$$ coins from gifts altogether, must be new in Ivan's collection.

But his friends don't know which coins have Ivan already got in his collection. They don't want to spend money so they want to buy minimum quantity of coins, that satisfy all terms, irrespective of the Ivan's collection. Help them to find this minimum number of coins or define it's not possible to meet all the terms.

## Input Format
The only line of input contains 4 integers $$$N$$$, $$$M$$$, $$$K$$$, $$$L$$$ ($$$1 \le K \le N \le 10^{18}$$$; $$$1 \le M, \,\, L \le 10^{18}$$$) — quantity of different coins, number of Ivan's friends, size of Ivan's collection and quantity of coins, that must be new in Ivan's collection.

## Output Format
Print one number — minimal number of coins one friend can gift to satisfy all the conditions. If it is impossible to satisfy all three conditions print "-1" (without quotes).

## Examples
```input
20 15 2 3
```
```output
1
```
-----
```input
10 11 2 4
```
```output
-1
```

## Note
In the first test, one coin from each friend is enough, as he will be presented with 15 different coins and 13 of them will definitely be new.

In the second test, Ivan has 11 friends, but there are only 10 different coins. So all friends can't present him different coins.

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
Ivan has number $$$b$$$. He is sorting through the numbers $$$a$$$ from $$$1$$$ to $$$10^{18}$$$, and for every $$$a$$$ writes $$$\frac{[a, \,\, b]}{a}$$$ on blackboard. Here $$$[a, \,\, b]$$$ stands for least common multiple of $$$a$$$ and $$$b$$$. Ivan is very lazy, that's why this task bored him soon. But he is interested in how many different numbers he would write on the board if he would finish the task. Help him to find the quantity of different numbers he would write on the board.

## Input Format
The only line contains one integer — $$$b$$$ $$$(1 \le b \le 10^{10})$$$.

## Output Format
Print one number — answer for the problem.

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

## Note
In the first example $$$[a, \,\, 1] = a$$$, therefore $$$\frac{[a, \,\, b]}{a}$$$ is always equal to $$$1$$$.

In the second example $$$[a, \,\, 2]$$$ can be equal to $$$a$$$ or $$$2 \cdot a$$$ depending on parity of $$$a$$$. $$$\frac{[a, \,\, b]}{a}$$$ can be equal to $$$1$$$ and $$$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
Ivan is a novice painter. He has $$$n$$$ dyes of different colors. He also knows exactly $$$m$$$ pairs of colors which harmonize with each other.

Ivan also enjoy playing chess. He has $$$5000$$$ rooks. He wants to take $$$k$$$ rooks, paint each of them in one of $$$n$$$ colors and then place this $$$k$$$ rooks on a chessboard of size $$$10^{9} \times 10^{9}$$$.

Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal.

Ivan wants his arrangement of rooks to have following properties:

- For any color there is a rook of this color on a board;
- For any color the set of rooks of this color is connected;
- For any two different colors $$$a$$$ $$$b$$$ union of set of rooks of color $$$a$$$ and set of rooks of color $$$b$$$ is connected if and only if this two colors harmonize with each other.

Please help Ivan find such an arrangement.

## Input Format
The first line of input contains $$$2$$$ integers $$$n$$$, $$$m$$$ ($$$1 \le n \le 100$$$, $$$0 \le m \le min(1000, \,\, \frac{n(n-1)}{2})$$$) — number of colors and number of pairs of colors which harmonize with each other.

In next $$$m$$$ lines pairs of colors which harmonize with each other are listed. Colors are numbered from $$$1$$$ to $$$n$$$. It is guaranteed that no pair occurs twice in this list.

## Output Format
Print $$$n$$$ blocks, $$$i$$$-th of them describes rooks of $$$i$$$-th color.

In the first line of block print one number $$$a_{i}$$$ ($$$1 \le a_{i} \le 5000$$$) — number of rooks of color $$$i$$$. In each of next $$$a_{i}$$$ lines print two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, \,\, y \le 10^{9}$$$) — coordinates of the next rook.

All rooks must be on different cells.

Total number of rooks must not exceed $$$5000$$$.

It is guaranteed that the solution exists.

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

## Note
Rooks arrangements for all three examples (red is color $$$1$$$, green is color $$$2$$$ and blue is color $$$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 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
Chouti was doing a competitive programming competition. However, after having all the problems accepted, he got bored and decided to invent some small games.

He came up with the following game. The player has a positive integer $$$n$$$. Initially the value of $$$n$$$ equals to $$$v$$$ and the player is able to do the following operation as many times as the player want (possibly zero): choose a positive integer $$$x$$$ that $$$x<n$$$ and $$$x$$$ is not a divisor of $$$n$$$, then subtract $$$x$$$ from $$$n$$$. The goal of the player is to minimize the value of $$$n$$$ in the end.

Soon, Chouti found the game trivial. Can you also beat the game?

## Input Format
The input contains only one integer in the first line: $$$v$$$ ($$$1 \le v \le 10^9$$$), the initial value of $$$n$$$.

## Output Format
Output a single integer, the minimum value of $$$n$$$ the player can get.

## Examples
```input
8
```
```output
1
```
-----
```input
1
```
```output
1
```

## Note
In the first example, the player can choose $$$x=3$$$ in the first turn, then $$$n$$$ becomes $$$5$$$. He can then choose $$$x=4$$$ in the second turn to get $$$n=1$$$ as the result. There are other ways to get this minimum. However, for example, he cannot choose $$$x=2$$$ in the first turn because $$$2$$$ is a divisor of $$$8$$$.

In the second example, since $$$n=1$$$ initially, the player can do nothing.

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
Chouti and his classmates are going to the university soon. To say goodbye to each other, the class has planned a big farewell party in which classmates, teachers and parents sang and danced.

Chouti remembered that $$$n$$$ persons took part in that party. To make the party funnier, each person wore one hat among $$$n$$$ kinds of weird hats numbered $$$1, 2, \ldots n$$$. It is possible that several persons wore hats of the same kind. Some kinds of hats can remain unclaimed by anyone.

After the party, the $$$i$$$-th person said that there were $$$a_i$$$ persons wearing a hat differing from his own.

It has been some days, so Chouti forgot all about others' hats, but he is curious about that. Let $$$b_i$$$ be the number of hat type the $$$i$$$-th person was wearing, Chouti wants you to find any possible $$$b_1, b_2, \ldots, b_n$$$ that doesn't contradict with any person's statement. Because some persons might have a poor memory, there could be no solution at all.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of persons in the party.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n-1$$$), the statements of people.

## Output Format
If there is no solution, print a single line "Impossible".

Otherwise, print "Possible" and then $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$).

If there are multiple answers, print any of them.

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

## Note
In the answer to the first example, all hats are the same, so every person will say that there were no persons wearing a hat different from kind $$$1$$$.

In the answer to the second example, the first and the second person wore the hat with type $$$1$$$ and all other wore a hat of type $$$2$$$.

So the first two persons will say there were three persons with hats differing from their own. Similarly, three last persons will say there were two persons wearing a hat different from their own.

In the third example, it can be shown that no solution exists.

In the first and the second example, other possible configurations are possible.

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
On his free time, Chouti likes doing some housework. He has got one new task, paint some bricks in the yard.

There are $$$n$$$ bricks lined in a row on the ground. Chouti has got $$$m$$$ paint buckets of different colors at hand, so he painted each brick in one of those $$$m$$$ colors.

Having finished painting all bricks, Chouti was satisfied. He stood back and decided to find something fun with these bricks. After some counting, he found there are $$$k$$$ bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure).

So as usual, he needs your help in counting how many ways could he paint the bricks. Two ways of painting bricks are different if there is at least one brick painted in different colors in these two ways. Because the answer might be quite big, you only need to output the number of ways modulo $$$998\,244\,353$$$.

## Input Format
The first and only line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n,m \leq 2000, 0 \leq k \leq n-1$$$) — the number of bricks, the number of colors, and the number of bricks, such that its color differs from the color of brick to the left of it.

## Output Format
Print one integer — the number of ways to color bricks modulo $$$998\,244\,353$$$.

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

## Note
In the first example, since $$$k=0$$$, the color of every brick should be the same, so there will be exactly $$$m=3$$$ ways to color the bricks.

In the second example, suppose the two colors in the buckets are yellow and lime, the following image shows all $$$4$$$ possible colorings.

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
Chouti was tired of the tedious homework, so he opened up an old programming problem he created years ago.

You are given a connected undirected graph with $$$n$$$ vertices and $$$m$$$ weighted edges. There are $$$k$$$ special vertices: $$$x_1, x_2, \ldots, x_k$$$.

Let's define the cost of the path as the maximum weight of the edges in it. And the distance between two vertexes as the minimum cost of the paths connecting them.

For each special vertex, find another special vertex which is farthest from it (in terms of the previous paragraph, i.e. the corresponding distance is maximum possible) and output the distance between them.

The original constraints are really small so he thought the problem was boring. Now, he raises the constraints and hopes you can solve it for him.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \leq k \leq n \leq 10^5$$$, $$$n-1 \leq m \leq 10^5$$$) — the number of vertices, the number of edges and the number of special vertices.

The second line contains $$$k$$$ distinct integers $$$x_1, x_2, \ldots, x_k$$$ ($$$1 \leq x_i \leq n$$$).

Each of the following $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ ($$$1 \leq u,v \leq n, 1 \leq w \leq 10^9$$$), denoting there is an edge between $$$u$$$ and $$$v$$$ of weight $$$w$$$. The given graph is undirected, so an edge $$$(u, v)$$$ can be used in the both directions.

The graph may have multiple edges and self-loops.

It is guaranteed, that the graph is connected.

## Output Format
The first and only line should contain $$$k$$$ integers. The $$$i$$$-th integer is the distance between $$$x_i$$$ and the farthest special vertex from it.

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

## Note
In the first example, the distance between vertex $$$1$$$ and $$$2$$$ equals to $$$2$$$ because one can walk through the edge of weight $$$2$$$ connecting them. So the distance to the farthest node for both $$$1$$$ and $$$2$$$ equals to $$$2$$$.

In the second example, one can find that distance between $$$1$$$ and $$$2$$$, distance between $$$1$$$ and $$$3$$$ are both $$$3$$$ and the distance between $$$2$$$ and $$$3$$$ is $$$2$$$.

The graph may have multiple edges between and self-loops, as in the first example.

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
Chouti is working on a strange math problem.

There was a sequence of $$$n$$$ positive integers $$$x_1, x_2, \ldots, x_n$$$, where $$$n$$$ is even. The sequence was very special, namely for every integer $$$t$$$ from $$$1$$$ to $$$n$$$, $$$x_1+x_2+...+x_t$$$ is a square of some integer number (that is, a perfect square).

Somehow, the numbers with odd indexes turned to be missing, so he is only aware of numbers on even positions, i.e. $$$x_2, x_4, x_6, \ldots, x_n$$$. The task for him is to restore the original sequence. Again, it's your turn to help him.

The problem setter might make mistakes, so there can be no possible sequence at all. If there are several possible sequences, you can output any.

## Input Format
The first line contains an even number $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line contains $$$\frac{n}{2}$$$ positive integers $$$x_2, x_4, \ldots, x_n$$$ ($$$1 \le x_i \le 2 \cdot 10^5$$$).

## Output Format
If there are no possible sequence, print "No".

Otherwise, print "Yes" and then $$$n$$$ positive integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^{13}$$$), where $$$x_2, x_4, \ldots, x_n$$$ should be same as in input data. If there are multiple answers, print any.

Note, that the limit for $$$x_i$$$ is larger than for input data. It can be proved that in case there is an answer, there must be a possible sequence satisfying $$$1 \le x_i \le 10^{13}$$$.

## Examples
```input
6
5 11 44
```
```output
Yes
4 5 16 11 64 44
```
-----
```input
2
9900
```
```output
Yes
100 9900
```
-----
```input
6
314 1592 6535
```
```output
No
```

## Note
In the first example

- $$$x_1=4$$$
- $$$x_1+x_2=9$$$
- $$$x_1+x_2+x_3=25$$$
- $$$x_1+x_2+x_3+x_4=36$$$
- $$$x_1+x_2+x_3+x_4+x_5=100$$$
- $$$x_1+x_2+x_3+x_4+x_5+x_6=144$$$

In the second example, $$$x_1=100$$$, $$$x_1+x_2=10000$$$. They are all perfect squares. There're other answers possible. For example, $$$x_1=22500$$$ is another answer.

In the third example, it is possible to show, that no such sequence exists.

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
Chouti thought about his very first days in competitive programming. When he had just learned to write merge sort, he thought that the merge sort is too slow, so he restricted the maximum depth of recursion and modified the merge sort to the following:

Chouti found his idea dumb since obviously, this "merge sort" sometimes cannot sort the array correctly. However, Chouti is now starting to think of how good this "merge sort" is. Particularly, Chouti wants to know for a random permutation $$$a$$$ of $$$1, 2, \ldots, n$$$ the expected number of inversions after calling MergeSort(a, 1, n, k).

It can be proved that the expected number is rational. For the given prime $$$q$$$, suppose the answer can be denoted by $$$\frac{u}{d}$$$ where $$$gcd(u,d)=1$$$, you need to output an integer $$$r$$$ satisfying $$$0 \le r<q$$$ and $$$rd \equiv u \pmod q$$$. It can be proved that such $$$r$$$ exists and is unique.

## Input Format
The first and only line contains three integers $$$n, k, q$$$ ($$$1 \leq n, k \leq 10^5, 10^8 \leq q \leq 10^9$$$, $$$q$$$ is a prime).

## Output Format
The first and only line contains an integer $$$r$$$.

## Examples
```input
3 1 998244353
```
```output
499122178
```
-----
```input
3 2 998244353
```
```output
665496236
```
-----
```input
9 3 998244353
```
```output
449209967
```
-----
```input
9 4 998244353
```
```output
665496237
```

## Note
In the first example, all possible permutations are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$.

With $$$k=1$$$, MergeSort(a, 1, n, k) will only return the original permutation. Thus the answer is $$$9/6=3/2$$$, and you should output $$$499122178$$$ because $$$499122178 \times 2 \equiv 3 \pmod {998244353}$$$.

In the second example, all possible permutations are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$ and the corresponding outputs of MergeSort(a, 1, n, k) are $$$[1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]$$$ respectively. Thus the answer is $$$4/6=2/3$$$, and you should output $$$665496236$$$ because $$$665496236 \times 3 \equiv 2 \pmod {998244353}$$$.

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
You are given an array $$$a$$$ consisting of $$$n$$$ integer numbers.

Let instability of the array be the following value: $$$\max\limits_{i = 1}^{n} a_i - \min\limits_{i = 1}^{n} a_i$$$.

You have to remove exactly one element from this array to minimize instability of the resulting $$$(n-1)$$$-elements array. Your task is to calculate the minimum possible instability.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of elements in the array $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — elements of the array $$$a$$$.

## Output Format
Print one integer — the minimum possible instability of the array if you have to remove exactly one element from the array $$$a$$$.

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

## Note
In the first example you can remove $$$7$$$ then instability of the remaining array will be $$$3 - 1 = 2$$$.

In the second example you can remove either $$$1$$$ or $$$100000$$$ then instability of the remaining array will be $$$100000 - 100000 = 0$$$ and $$$1 - 1 = 0$$$ correspondingly.

Now solve the problem and return the code.