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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Find out if it is possible to partition the first $$$n$$$ positive integers into two non-empty disjoint sets $$$S_1$$$ and $$$S_2$$$ such that:

$$$\mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) > 1$$$

Here $$$\mathrm{sum}(S)$$$ denotes the sum of all elements present in set $$$S$$$ and $$$\mathrm{gcd}$$$ means thegreatest common divisor.

Every integer number from $$$1$$$ to $$$n$$$ should be present in exactly one of $$$S_1$$$ or $$$S_2$$$.

## Input Format
The only line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 45\,000$$$)

## Output Format
If such partition doesn't exist, print "No" (quotes for clarity).

Otherwise, print "Yes" (quotes for clarity), followed by two lines, describing $$$S_1$$$ and $$$S_2$$$ respectively.

Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty.

If there are multiple possible partitions — print any of them.

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

## Note
In the first example, there is no way to partition a single number into two non-empty sets, hence the answer is "No".

In the second example, the sums of the sets are $$$2$$$ and $$$4$$$ respectively. The $$$\mathrm{gcd}(2, 4) = 2 > 1$$$, hence that is one of the possible answers.

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
There are $$$n$$$ slimes in a row. Each slime has an integer value (possibly negative or zero) associated with it.

Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists).

When a slime with a value $$$x$$$ eats a slime with a value $$$y$$$, the eaten slime disappears, and the value of the remaining slime changes to $$$x - y$$$.

The slimes will eat each other until there is only one slime left.

Find the maximum possible value of the last slime.

## Input Format
The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 500\,000$$$) denoting the number of slimes.

The next line contains $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$), where $$$a_i$$$ is the value of $$$i$$$-th slime.

## Output Format
Print an only integer — the maximum possible value of the last slime.

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

## Note
In the first example, a possible way of getting the last slime with value $$$4$$$ is:

- Second slime eats the third slime, the row now contains slimes $$$2, -1, 1$$$
- Second slime eats the third slime, the row now contains slimes $$$2, -2$$$
- First slime eats the second slime, the row now contains $$$4$$$

In the second example, the first slime can keep eating slimes to its right to end up with a value of $$$4$$$.

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
You are given a binary string $$$s$$$.

Find the number of distinct cyclical binary strings of length $$$n$$$ which contain $$$s$$$ as a substring.

The cyclical string $$$t$$$ contains $$$s$$$ as a substring if there is some cyclical shift of string $$$t$$$, such that $$$s$$$ is a substring of this cyclical shift of $$$t$$$.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 40$$$) — the length of the target string $$$t$$$.

The next line contains the string $$$s$$$ ($$$1 \le |s| \le n$$$) — the string which must be a substring of cyclical string $$$t$$$. String $$$s$$$ contains only characters '0' and '1'.

## Output Format
Print the only integer — the number of distinct cyclical binary strings $$$t$$$, which contain $$$s$$$ as a substring.

## Examples
```input
2
0
```
```output
3
```
-----
```input
4
1010
```
```output
2
```
-----
```input
20
10101010101010
```
```output
962
```

## Note
In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".

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
There are $$$n$$$ benches in the Berland Central park. It is known that $$$a_i$$$ people are currently sitting on the $$$i$$$-th bench. Another $$$m$$$ people are coming to the park and each of them is going to have a seat on some bench out of $$$n$$$ available.

Let $$$k$$$ be the maximum number of people sitting on one bench after additional $$$m$$$ people came to the park. Calculate the minimum possible $$$k$$$ and the maximum possible $$$k$$$.

Nobody leaves the taken seat during the whole process.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 100)$$$ — the number of benches in the park.

The second line contains a single integer $$$m$$$ $$$(1 \le m \le 10\,000)$$$ — the number of people additionally coming to the park.

Each of the next $$$n$$$ lines contains a single integer $$$a_i$$$ $$$(1 \le a_i \le 100)$$$ — the initial number of people on the $$$i$$$-th bench.

## Output Format
Print the minimum possible $$$k$$$ and the maximum possible $$$k$$$, where $$$k$$$ is the maximum number of people sitting on one bench after additional $$$m$$$ people came to the park.

## Examples
```input
4
6
1
1
1
1
```
```output
3 7
```
-----
```input
1
10
5
```
```output
15 15
```
-----
```input
3
6
1
6
5
```
```output
6 12
```
-----
```input
3
7
1
6
5
```
```output
7 13
```

## Note
In the first example, each of four benches is occupied by a single person. The minimum $$$k$$$ is $$$3$$$. For example, it is possible to achieve if two newcomers occupy the first bench, one occupies the second bench, one occupies the third bench, and two remaining — the fourth bench. The maximum $$$k$$$ is $$$7$$$. That requires all six new people to occupy the same bench.

The second example has its minimum $$$k$$$ equal to $$$15$$$ and maximum $$$k$$$ equal to $$$15$$$, as there is just a single bench in the park and all $$$10$$$ people will occupy it.

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
Petya has an array $$$a$$$ consisting of $$$n$$$ integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.

Now he wonders what is the number of segments in his array with the sum less than $$$t$$$. Help Petya to calculate this number.

More formally, you are required to calculate the number of pairs $$$l, r$$$ ($$$l \le r$$$) such that $$$a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$$$).

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$|a_{i}| \le 10^{9}$$$) — the description of Petya's array. Note that there might be negative, zero and positive elements.

## Output Format
Print the number of segments in Petya's array with the sum of elements less than $$$t$$$.

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

## Note
In the first example the following segments have sum less than $$$4$$$:

- $$$[2, 2]$$$, sum of elements is $$$-1$$$
- $$$[2, 3]$$$, sum of elements is $$$2$$$
- $$$[3, 3]$$$, sum of elements is $$$3$$$
- $$$[4, 5]$$$, sum of elements is $$$3$$$
- $$$[5, 5]$$$, sum of elements is $$$-1$$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
You are given an undirected tree, consisting of $$$n$$$ vertices.

The vertex is called a leaf if it has exactly one vertex adjacent to it.

The distance between some pair of vertices is the number of edges in the shortest path between them.

Let's call some set of leaves beautiful if the maximum distance between any pair of leaves in it is less or equal to $$$k$$$.

You want to split all leaves into non-intersecting beautiful sets. What is the minimal number of sets in such a split?

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le k \le 10^6$$$) — the number of vertices in the tree and the maximum distance between any pair of leaves in each beautiful set.

Each of the next $$$n - 1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — the description of the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

## Output Format
Print a single integer — the minimal number of beautiful sets the split can have.

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

## Note
Here is the graph for 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two arrays $$$a_0, a_1, \ldots, a_{n - 1}$$$ and $$$b_0, b_1, \ldots, b_{m-1}$$$, and an integer $$$c$$$.

Compute the following sum:

$$$$$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i b_j c^{i^2\,j^3}$$$$$$

Since it's value can be really large, print it modulo $$$490019$$$.

## Input Format
First line contains three integers $$$n$$$, $$$m$$$ and $$$c$$$ ($$$1 \le n, m \le 100\,000$$$, $$$1 \le c < 490019$$$).

Next line contains exactly $$$n$$$ integers $$$a_i$$$ and defines the array $$$a$$$ ($$$0 \le a_i \le 1000$$$).

Last line contains exactly $$$m$$$ integers $$$b_i$$$ and defines the array $$$b$$$ ($$$0 \le b_i \le 1000$$$).

## Output Format
Print one integer — value of the sum modulo $$$490019$$$.

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

## Note
In the first example, the only non-zero summand corresponds to $$$i = 1$$$, $$$j = 1$$$ and is equal to $$$1 \cdot 1 \cdot 3^1 = 3$$$.

In the second example, all summands are equal to $$$1$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Vasya has got an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. This graph doesn't contain any self-loops or multiple edges. Self-loop is an edge connecting a vertex to itself. Multiple edges are a pair of edges such that they connect the same pair of vertices. Since the graph is undirected, the pair of edges $$$(1, 2)$$$ and $$$(2, 1)$$$ is considered to be multiple edges. Isolated vertex of the graph is a vertex such that there is no edge connecting this vertex to any other vertex.

Vasya wants to know the minimum and maximum possible number of isolated vertices in an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges.

## Input Format
The only line contains two integers $$$n$$$ and $$$m~(1 \le n \le 10^5, 0 \le m \le \frac{n (n - 1)}{2})$$$.

It is guaranteed that there exists a graph without any self-loops or multiple edges with such number of vertices and edges.

## Output Format
In the only line print two numbers $$$min$$$ and $$$max$$$ — the minimum and maximum number of isolated vertices, respectively.

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

## Note
In the first example it is possible to construct a graph with $$$0$$$ isolated vertices: for example, it should contain edges $$$(1, 2)$$$ and $$$(3, 4)$$$. To get one isolated vertex, we may construct a graph with edges $$$(1, 2)$$$ and $$$(1, 3)$$$.

In the second example the graph will always contain exactly one isolated vertex.

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
There is a toy building consisting of $$$n$$$ towers. Each tower consists of several cubes standing on each other. The $$$i$$$-th tower consists of $$$h_i$$$ cubes, so it has height $$$h_i$$$.

Let's define operation slice on some height $$$H$$$ as following: for each tower $$$i$$$, if its height is greater than $$$H$$$, then remove some top cubes to make tower's height equal to $$$H$$$. Cost of one "slice" equals to the total number of removed cubes from all towers.

Let's name slice as good one if its cost is lower or equal to $$$k$$$ ($$$k \ge n$$$).

Calculate the minimum number of good slices you have to do to make all towers have the same height. Of course, it is always possible to make it so.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le k \le 10^9$$$) — the number of towers and the restriction on slices, respectively.

The second line contains $$$n$$$ space separated integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 2 \cdot 10^5$$$) — the initial heights of towers.

## Output Format
Print one integer — the minimum number of good slices you have to do to make all towers have the same heigth.

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

## Note
In the first example it's optimal to make $$$2$$$ slices. The first slice is on height $$$2$$$ (its cost is $$$3$$$), and the second one is on height $$$1$$$ (its cost is $$$4$$$).

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
You stumbled upon a new kind of chess puzzles. The chessboard you are given is not necesserily $$$8 \times 8$$$, but it still is $$$N \times N$$$. Each square has some number written on it, all the numbers are from $$$1$$$ to $$$N^2$$$ and all the numbers are pairwise distinct. The $$$j$$$-th square in the $$$i$$$-th row has a number $$$A_{ij}$$$ written on it.

In your chess set you have only three pieces: a knight, a bishop and a rook. At first, you put one of them on the square with the number $$$1$$$ (you can choose which one). Then you want to reach square $$$2$$$ (possibly passing through some other squares in process), then square $$$3$$$ and so on until you reach square $$$N^2$$$. In one step you are allowed to either make a valid move with the current piece or replace it with some other piece. Each square can be visited arbitrary number of times.

A knight can move to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. A bishop moves diagonally. A rook moves horizontally or vertically. The move should be performed to a different square from the one a piece is currently standing on.

You want to minimize the number of steps of the whole traversal. Among all the paths to have the same number of steps you want to choose the one with the lowest number of piece replacements.

What is the path you should take to satisfy all conditions?

## Input Format
The first line contains a single integer $$$N$$$ ($$$3 \le N \le 10$$$) — the size of the chessboard.

Each of the next $$$N$$$ lines contains $$$N$$$ integers $$$A_{i1}, A_{i2}, \dots, A_{iN}$$$ ($$$1 \le A_{ij} \le N^2$$$) — the numbers written on the squares of the $$$i$$$-th row of the board.

It is guaranteed that all $$$A_{ij}$$$ are pairwise distinct.

## Output Format
The only line should contain two integers — the number of steps in the best answer and the number of replacement moves in it.

## Examples
```input
3
1 9 3
8 6 7
4 2 5
```
```output
12 1
```

## Note
Here are the steps for the first example (the starting piece is a knight):

1. Move to $$$(3, 2)$$$
2. Move to $$$(1, 3)$$$
3. Move to $$$(3, 2)$$$
4. Replace the knight with a rook
5. Move to $$$(3, 1)$$$
6. Move to $$$(3, 3)$$$
7. Move to $$$(3, 2)$$$
8. Move to $$$(2, 2)$$$
9. Move to $$$(2, 3)$$$
10. Move to $$$(2, 1)$$$
11. Move to $$$(1, 1)$$$
12. Move to $$$(1, 2)$$$

Now solve the problem and return the code.