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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given array $$$a_1, a_2, \dots, a_n$$$. You need to split it into $$$k$$$ subsegments (so every element is included in exactly one subsegment).

The weight of a subsegment $$$a_l, a_{l+1}, \dots, a_r$$$ is equal to $$$(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$$$. The weight of a partition is a total weight of all its segments.

Find the partition of minimal weight.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^4$$$, $$$1 \le k \le \min(100, n)$$$) — the length of the array $$$a$$$ and the number of subsegments in the partition.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^4$$$) — the array $$$a$$$.

## Output Format
Print single integer — the minimal weight among all possible partitions.

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

## Note
The optimal partition in the first example is next: $$$6$$$ $$$1$$$ $$$7$$$ $$$\bigg|$$$ $$$4$$$.

The optimal partition in the second example is next: $$$6$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$7$$$ $$$4$$$.

One of the optimal partitions in the third example is next: $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$5$$$.

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
Melody Pond was stolen from her parents as a newborn baby by Madame Kovarian, to become a weapon of the Silence in their crusade against the Doctor. Madame Kovarian changed Melody's name to River Song, giving her a new identity that allowed her to kill the Eleventh Doctor.

Heidi figured out that Madame Kovarian uses a very complicated hashing function in order to change the names of the babies she steals. In order to prevent this from happening to future Doctors, Heidi decided to prepare herself by learning some basic hashing techniques.

The first hashing function she designed is as follows.

Given two positive integers $$$(x, y)$$$ she defines $$$H(x,y):=x^2+2xy+x+1$$$.

Now, Heidi wonders if the function is reversible. That is, given a positive integer $$$r$$$, can you find a pair $$$(x, y)$$$ (of positive integers) such that $$$H(x, y) = r$$$?

If multiple such pairs exist, output the one with smallest possible $$$x$$$. If there is no such pair, output "NO".

## Input Format
The first and only line contains an integer $$$r$$$ ($$$1 \le r \le 10^{12}$$$).

## Output Format
Output integers $$$x, y$$$ such that $$$H(x,y) = r$$$ and $$$x$$$ is smallest possible, or "NO" if no such pair exists.

## Examples
```input
19
```
```output
1 8
```
-----
```input
16
```
```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
After learning about polynomial hashing, Heidi decided to learn about shift-xor hashing. In particular, she came across this interesting problem.

Given a bitstring $$$y \in \{0,1\}^n$$$ find out the number of different $$$k$$$ ($$$0 \leq k < n$$$) such that there exists $$$x \in \{0,1\}^n$$$ for which $$$y = x \oplus \mbox{shift}^k(x).$$$

In the above, $$$\oplus$$$ is the xor operation and $$$\mbox{shift}^k$$$ is the operation of shifting a bitstring cyclically to the right $$$k$$$ times. For example, $$$001 \oplus 111 = 110$$$ and $$$\mbox{shift}^3(00010010111000) = 00000010010111$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the bitstring $$$y$$$.

The second line contains the bitstring $$$y$$$.

## Output Format
Output a single integer: the number of suitable values of $$$k$$$.

## Examples
```input
4
1010
```
```output
3
```

## Note
In the first example:

- $$$1100\oplus \mbox{shift}^1(1100) = 1010$$$
- $$$1000\oplus \mbox{shift}^2(1000) = 1010$$$
- $$$0110\oplus \mbox{shift}^3(0110) = 1010$$$

There is no $$$x$$$ such that $$$x \oplus x = 1010$$$, hence the answer is $$$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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Now Heidi is ready to crack Madame Kovarian's hashing function.

Madame Kovarian has a very strict set of rules for name changes. Two names can be interchanged only if using the following hashing function on them results in a collision. However, the hashing function is parametrized, so one can always find a set of parameters that causes such a collision. Heidi decided to exploit this to her advantage.

Given two strings $$$w_1$$$, $$$w_2$$$ of equal length $$$n$$$ consisting of lowercase English letters and an integer $$$m$$$.

Consider the standard polynomial hashing function:

$$$H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \mbox{mod}(p)$$$

where $$$p$$$ is some prime, and $$$r$$$ is some number such that $$$2\leq r \leq p-2$$$.

The goal is to find $$$r$$$ and a prime $$$p$$$ ($$$m \leq p \leq 10^9$$$) such that $$$H_p(w_1) = H_p(w_2)$$$.

Strings $$$w_1$$$ and $$$w_2$$$ are sampled independently at random from all strings of length $$$n$$$ over lowercase English letters.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$10 \le n \le 10^5$$$, $$$2 \le m \le 10^5$$$).

The second and the third line, respectively, contain the words $$$w_1$$$, $$$w_2$$$ that were sampled independently at random from all strings of length $$$n$$$ over lowercase English letters.

## Output Format
Output integers $$$p, r$$$.

$$$p$$$ should be a prime in the range $$$[m, 10^9]$$$ and $$$r$$$ should be an integer satisfying $$$r\in [2,p-2]$$$.

At least one solution is guaranteed to exist. In case multiple solutions exist, print any of them.

## Examples
```input
10 5
bgcbaaaaaa
cccaaaaaaa
```
```output
5 2
```
-----
```input
10 100
melodypond
riversongg
```
```output
118219 79724
```

## Note
In the first example, note that even though $$$p=3$$$ and $$$r=2$$$ also causes a colision of hashes, it is not a correct solution, since $$$m$$$ is $$$5$$$ and thus we want $$$p\geq 5$$$.

In the second example, we are aware of the extra 'g' at the end. We just didn't realize that "River Song" and "Melody Pond" have different lengths...

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
Heidi and Doctor Who hopped out of the TARDIS and found themselves at EPFL in 2018. They were surrounded by stormtroopers and Darth Vader was approaching. Miraculously, they managed to escape to a nearby rebel base but the Doctor was very confused. Heidi reminded him that last year's HC2 theme was Star Wars. Now he understood, and he's ready to face the evils of the Empire!

The rebels have $$$s$$$ spaceships, each with a certain attacking power $$$a$$$.

They want to send their spaceships to destroy the empire bases and steal enough gold and supplies in order to keep the rebellion alive.

The empire has $$$b$$$ bases, each with a certain defensive power $$$d$$$, and a certain amount of gold $$$g$$$.

A spaceship can attack all the bases which have a defensive power less than or equal to its attacking power.

If a spaceship attacks a base, it steals all the gold in that base.

The rebels are still undecided which spaceship to send out first, so they asked for the Doctor's help. They would like to know, for each spaceship, the maximum amount of gold it can steal.

## Input Format
The first line contains integers $$$s$$$ and $$$b$$$ ($$$1 \leq s, b \leq 10^5$$$), the number of spaceships and the number of bases, respectively.

The second line contains $$$s$$$ integers $$$a$$$ ($$$0 \leq a \leq 10^9$$$), the attacking power of each spaceship.

The next $$$b$$$ lines contain integers $$$d, g$$$ ($$$0 \leq d \leq 10^9$$$, $$$0 \leq g \leq 10^4$$$), the defensive power and the gold of each base, respectively.

## Output Format
Print $$$s$$$ integers, the maximum amount of gold each spaceship can steal, in the same order as the spaceships are given in the input.

## Examples
```input
5 4
1 3 5 2 4
0 1
4 2
2 8
9 4
```
```output
1 9 11 9 11
```

## Note
The first spaceship can only attack the first base.

The second spaceship can attack the first and third bases.

The third spaceship can attack the first, second and third bases.

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
The Cybermen and the Daleks have long been the Doctor's main enemies. Everyone knows that both these species enjoy destroying everything they encounter. However, a little-known fact about them is that they both also love taking Turing tests!

Heidi designed a series of increasingly difficult tasks for them to spend their time on, which would allow the Doctor enough time to save innocent lives!

The funny part is that these tasks would be very easy for a human to solve.

The first task is as follows. There are some points on the plane. All but one of them are on the boundary of an axis-aligned square (its sides are parallel to the axes). Identify that point.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 10$$$).

Each of the following $$$4n + 1$$$ lines contains two integers $$$x_i, y_i$$$ ($$$0 \leq x_i, y_i \leq 50$$$), describing the coordinates of the next point.

It is guaranteed that there are at least $$$n$$$ points on each side of the square and all $$$4n + 1$$$ points are distinct.

## Output Format
Print two integers — the coordinates of the point that is not on the boundary of the square.

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

## Note
In both examples, the square has four sides $$$x=0$$$, $$$x=2$$$, $$$y=0$$$, $$$y=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
The Cybermen solved that first test much quicker than the Daleks. Luckily for us, the Daleks were angry (shocking!) and they destroyed some of the Cybermen.

After the fighting stopped, Heidi gave them another task to waste their time on.

There are $$$n$$$ points on a plane. Given a radius $$$r$$$, find the maximum number of points that can be covered by an $$$L^1$$$-ball with radius $$$r$$$.

An $$$L^1$$$-ball with radius $$$r$$$ and center $$$(x_0, y_0)$$$ in a 2D-plane is defined as the set of points $$$(x, y)$$$ such that the Manhattan distance between $$$(x_0, y_0)$$$ and $$$(x, y)$$$ is at most $$$r$$$.

Manhattan distance between $$$(x_0, y_0)$$$ and $$$(x, y)$$$ is defined as $$$|x - x_0| + |y - y_0|$$$.

## Input Format
The first line contains two integers $$$n, r$$$ ($$$1 \le n \le 300\,000, 1 \le r \le 10^6$$$), the number of points and the radius of the ball, respectively.

Each of the next $$$n$$$ lines contains integers $$$x_i, y_i$$$ ($$$-10^6 \leq x_i, y_i \leq 10^6$$$), describing the coordinates of the $$$i$$$-th point.

It is guaranteed, that all points are distinct.

## Output Format
Print one integer — the maximum number points that an $$$L^1$$$-ball with radius $$$r$$$ can cover.

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

## Note
In the first example, a ball centered at $$$(1, 0)$$$ covers the points $$$(1, 1)$$$, $$$(1, -1)$$$, $$$(2, 0)$$$.

In the second example, a ball centered at $$$(0, 0)$$$ covers all the points.

Note that $$$x_0$$$ and $$$y_0$$$ need not be integer.

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
Heidi enjoyed performing the simulation because she knew exactly when a new universe would be formed and where, and when a non-existent link would be broken and where.

However, the multiverse itself works in mysterious ways. Well, it works using probabilities, which to some people is mysterious.

At each unit time, when a decision is made, one of the two events will happen randomly. Let's denote $$$l$$$ as the current length of the multiverse. With a probability of $$$p_{create} = 1 - \frac{l}{m}$$$, a universe will be created. With a probability of $$$p_{break}=\frac{l}{m}$$$, a non-existent link will be broken at some position.

More specifically,

- When a universe is created, it will manifest itself between any two adjacent universes or at one of the ends. Each position occurs with a probability of $$$\frac{1}{l + 1}$$$.
- When a link is broken, it could be cut between any two adjacent universes, each with a probability of $$$\frac{1}{l-1}$$$. After separating the multiverse into two segments, the segment NOT containing the Doctor will cease to exist.

As earlier, the Doctor remains in the same universe. However, if at some point the multiverse breaks in such a way that the Doctor finds himself at the leftmost or rightmost end of it, the TARDIS stops functioning.

In such a case, the Doctor must actually walk across the multiverse to find the tools to fix it.

We are interested in the expected value of the length of the multiverse when such an event occurs.

## Input Format
The first and only line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ $$$(1 \le k \le n \le m \le 250)$$$, the initial length of the multiverse, the initial position of the Doctor, and the maximum possible length of the multiverse.

## Output Format
Output a single integer on a single line, indicating the expected length of the multiverse.

If the answer is $$$\frac{p}{q}$$$, please print $$$r$$$ where $$$p \equiv r \cdot q (\text{mod } 10^9 + 7)$$$.

## Examples
```input
2 1 2
```
```output
2
```
-----
```input
2 2 10
```
```output
2
```
-----
```input
3 2 3
```
```output
2
```
-----
```input
3 2 5
```
```output
941659828
```
-----
```input
10 4 20
```
```output
196683114
```

## Note
For the first and the second test case, without any change to the multiverse, the Doctor is already at one of the ends.

For the third test case, the multiverse can only break at a position, which renders the Doctor at one of its ends.

For the fourth case, things seem to be a little more complicated, because the multiverse can grow and then be broken 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: 15.0 seconds
Memory limit: 256.0 MB

# Problem
After a successful field test, Heidi is considering deploying a trap along some Corridor, possibly not the first one. She wants to avoid meeting the Daleks inside the Time Vortex, so for abundance of caution she considers placing the traps only along those Corridors that are not going to be used according to the current Daleks' plan – which is to use a minimum spanning tree of Corridors. Heidi knows that all energy requirements for different Corridors are now different, and that the Daleks have a single unique plan which they are intending to use.

Your task is to calculate the number $$$E_{max}(c)$$$, which is defined in the same way as in the easy version – i.e., the largest $$$e \le 10^9$$$ such that if we changed the energy of corridor $$$c$$$ to $$$e$$$, the Daleks might use it – but now for every corridor that Heidi considers.

## Input Format
The first line: number $$$n$$$ of destinations, number $$$m$$$ of Time Corridors ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq 10^6$$$). The next $$$m$$$ lines: destinations $$$a$$$, $$$b$$$ and energy $$$e$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$, $$$0 \leq e \leq 10^9$$$).

No pair $$$\{a, b\}$$$ will repeat. The graph is guaranteed to be connected. All energy requirements $$$e$$$ are distinct.

## Output Format
Output $$$m-(n-1)$$$ lines, each containing one integer: $$$E_{max}(c_i)$$$ for the $$$i$$$-th Corridor $$$c_i$$$ from the input that is not part of the current Daleks' plan (minimum spanning tree).

## Examples
```input
3 3
1 2 8
2 3 3
3 1 4
```
```output
4
```

## Note
If $$$m = n-1$$$, then you need not output anything.

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

# Problem
With your help, Heidi has prepared a plan of trap placement and defence. Yet suddenly, the Doctor popped out of the TARDIS and told her that he had spied on the Daleks' preparations, and there is more of them than ever. Desperate times require desperate measures, so Heidi is going to risk meeting with the Daleks and she will consider placing a trap along any Corridor.

This means she needs your help again in calculating $$$E_{max}(c)$$$ – the largest $$$e \le 10^9$$$ such that if we changed the energy requirement of $$$c$$$ to $$$e$$$, then the Daleks might use $$$c$$$ in their invasion – but this time for all Time Corridors.

## Input Format
First line: number $$$n$$$ of destinations, number $$$m$$$ of corridors ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq 10^6$$$). The next $$$m$$$ lines: destinations $$$a$$$, $$$b$$$ and energy $$$e$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$, $$$0 \leq e \leq 10^9$$$).

No pair $$$\{a, b\}$$$ will repeat. The graph is guaranteed to be connected. It is not guaranteed that all energy requirements $$$e$$$ are distinct, or that the minimum spanning tree is unique.

## Output Format
Output $$$m$$$ lines, each containing one integer: $$$E_{max}(c_i)$$$ for the $$$i$$$-th Corridor $$$c_i$$$ from the input.

## Examples
```input
3 3
1 2 8
2 3 3
3 1 4
```
```output
4
8
8
```

Now solve the problem and return the code.