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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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.
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 c++17.

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is a square grid of size $$$n \times n$$$. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $$$\min(h, w)$$$ to color a rectangle of size $$$h \times w$$$. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of $$$m$$$ rectangles.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{9}$$$, $$$0 \le m \le 50$$$) — the size of the square grid and the number of black rectangles.

Each of the next $$$m$$$ lines contains 4 integers $$$x_{i1}$$$ $$$y_{i1}$$$ $$$x_{i2}$$$ $$$y_{i2}$$$ ($$$1 \le x_{i1} \le x_{i2} \le n$$$, $$$1 \le y_{i1} \le y_{i2} \le n$$$) — the coordinates of the bottom-left and the top-right corner cells of the $$$i$$$-th black rectangle.

The rectangles may intersect.

## Output Format
Print a single integer — the minimum total cost of painting the whole square in white.

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

## Note
The examples and some of optimal solutions are shown on the pictures below.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

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

Execution time limit: 0.5 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of $$$n$$$ integers. You need to split all integers into two groups so that the GCD of all integers in the first group is equal to one and the GCD of all integers in the second group is equal to one.

The GCD of a group of integers is the largest non-negative integer that divides all the integers in the group.

Both groups have to be non-empty.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

## Output Format
In the first line print "YES" (without quotes), if it is possible to split the integers into two groups as required, and "NO" (without quotes) otherwise.

If it is possible to split the integers, in the second line print $$$n$$$ integers, where the $$$i$$$-th integer is equal to $$$1$$$ if the integer $$$a_i$$$ should be in the first group, and $$$2$$$ otherwise.

If there are multiple solutions, print any.

## Examples
```input
4
2 3 6 7
```
```output
YES
2 2 1 1
```
-----
```input
5
6 15 35 77 22
```
```output
YES
2 1 2 1 1
```
-----
```input
5
6 10 15 1000 75
```
```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 c++17.

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

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You are given integers $$$n$$$, $$$k$$$. Let's consider the alphabet consisting of $$$k$$$ different elements.

Let beauty $$$f(s)$$$ of the string $$$s$$$ be the number of indexes $$$i$$$, $$$1\le i<|s|$$$, for which prefix of $$$s$$$ of length $$$i$$$ equals to suffix of $$$s$$$ of length $$$i$$$. For example, beauty of the string $$$abacaba$$$ equals $$$2$$$, as for $$$i = 1, 3$$$ prefix and suffix of length $$$i$$$ are equal.

Consider all words of length $$$n$$$ in the given alphabet. Find the expected value of $$$f(s)^2$$$ of a uniformly chosen at random word. We can show that it can be expressed as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime and $$$Q$$$ isn't divided by $$$10^9 + 7$$$. Output $$$P\cdot Q^{-1} \bmod 10^9 + 7$$$.

## Input Format
The first and the only line contains two integers $$$n$$$, $$$k$$$ ($$$1\le n \le 10^5$$$, $$$1\le k\le 10^9$$$) — the length of a string and the size of alphabet respectively.

## Output Format
Output a single integer — $$$P\times Q^{-1} \bmod 10^9 + 7$$$.

## Examples
```input
2 3
```
```output
333333336
```
-----
```input
1 5
```
```output
0
```
-----
```input
100 1
```
```output
9801
```
-----
```input
10 10
```
```output
412377396
```

## Note
In the first example, there are $$$9$$$ words of length $$$2$$$ in alphabet of size $$$3$$$ — $$$aa$$$, $$$ab$$$, $$$ac$$$, $$$ba$$$, $$$bb$$$, $$$bc$$$, $$$ca$$$, $$$cb$$$, $$$cc$$$. $$$3$$$ of them have beauty $$$1$$$ and $$$6$$$ of them have beauty $$$0$$$, so the average value is $$$\frac{1}{3}$$$.

In the third example, there is only one such word, and it has beauty $$$99$$$, so the average value is $$$99^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 c++17.

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Define the beauty of a permutation of numbers from $$$1$$$ to $$$n$$$ $$$(p_1, p_2, \dots, p_n)$$$ as number of pairs $$$(L, R)$$$ such that $$$1 \le L \le R \le n$$$ and numbers $$$p_L, p_{L+1}, \dots, p_R$$$ are consecutive $$$R-L+1$$$ numbers in some order. For example, the beauty of the permutation $$$(1, 2, 5, 3, 4)$$$ equals $$$9$$$, and segments, corresponding to pairs, are $$$[1]$$$, $$$[2]$$$, $$$[5]$$$, $$$[4]$$$, $$$[3]$$$, $$$[1, 2]$$$, $$$[3, 4]$$$, $$$[5, 3, 4]$$$, $$$[1, 2, 5, 3, 4]$$$.

Answer $$$q$$$ independent queries. In each query, you will be given integers $$$n$$$ and $$$k$$$. Determine if there exists a permutation of numbers from $$$1$$$ to $$$n$$$ with beauty equal to $$$k$$$, and if there exists, output one of them.

## Input Format
The first line contains a single integer $$$q$$$ ($$$1\le q \le 10\,000$$$) — the number of queries.

Follow $$$q$$$ lines. Each line contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le \frac{n(n+1)}{2}$$$) — the length of permutation and needed beauty respectively.

## Output Format
For a query output "NO", if such a permutation doesn't exist. Otherwise, output "YES", and in the next line output $$$n$$$ numbers — elements of permutation in the right order.

## Examples
```input
4
1 1
5 6
5 8
5 10
```
```output
YES
1 
YES
2 4 1 5 3 
NO
YES
2 3 1 4 5
```
-----
```input
2
4 10
100 1
```
```output
YES
1 2 3 4 
NO
```

## Note
Let's look at the first example.

The first query: in $$$(1)$$$ there is only one segment consisting of consecutive numbers — the entire permutation.

The second query: in $$$(2, 4, 1, 5, 3)$$$ there are $$$6$$$ such segments: $$$[2]$$$, $$$[4]$$$, $$$[1]$$$, $$$[5]$$$, $$$[3]$$$, $$$[2, 4, 1, 5, 3]$$$.

There is no such permutation for the second query.

The fourth query: in $$$(2, 3, 1, 4, 5)$$$ there are $$$10$$$ such segments: $$$[2]$$$, $$$[3]$$$, $$$[1]$$$, $$$[4]$$$, $$$[5]$$$, $$$[2, 3]$$$, $$$[2, 3, 1]$$$, $$$[2, 3, 1, 4]$$$, $$$[4, 5]$$$, $$$[2, 3, 1, 4, 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 c++17.

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Alice became interested in periods of integer numbers. We say positive $$$X$$$ integer number is periodic with length $$$L$$$ if there exists positive integer number $$$P$$$ with $$$L$$$ digits such that $$$X$$$ can be written as $$$PPPP…P$$$. For example:

$$$X = 123123123$$$ is periodic number with length $$$L = 3$$$ and $$$L = 9$$$

$$$X = 42424242$$$ is periodic number with length $$$L = 2,L = 4$$$ and $$$L = 8$$$

$$$X = 12345$$$ is periodic number with length $$$L = 5$$$

For given positive period length $$$L$$$ and positive integer number $$$A$$$, Alice wants to find smallest integer number $$$X$$$ strictly greater than $$$A$$$ that is periodic with length L.

## Input Format
First line contains one positive integer number $$$L \ (1 \leq L \leq 10^5)$$$ representing length of the period. Second line contains one positive integer number $$$A \ (1 \leq A \leq 10^{100 000})$$$.

## Output Format
One positive integer number representing smallest positive number that is periodic with length $$$L$$$ and is greater than $$$A$$$.

## Examples
```input
3
123456
```
```output
124124
```
-----
```input
3
12345
```
```output
100100
```

## Note
In first example 124124 is the smallest number greater than 123456 that can be written with period L = 3 (P = 124).

In the second example 100100 is the smallest number greater than 12345 with period L = 3 (P=100)

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 c++17.

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

Execution time limit: 0.5 seconds
Memory limit: 256.0 MB

# Problem
It is Bubble Cup finals season and farmer Johnny Bubbles must harvest his bubbles. The bubbles are in a rectangular bubblefield formed of $$$N$$$ x $$$M$$$ square parcels divided into $$$N$$$ rows and $$$M$$$ columns. The parcel in $$$i^{th}$$$ row and $$$j^{th}$$$ column yields $$$A_{i,j}$$$ bubbles.

Johnny Bubbles has available a very special self-driving bubble harvester that, once manually positioned at the beginning of a row or column, automatically harvests all the bubbles in that row or column. Once the harvester reaches the end of the row or column it stops and must be repositioned. The harvester can pass through any parcel any number of times, but it can collect bubbles from the parcel only once.

Johnny is very busy farmer, so he is available to manually position the harvester at most four times per day. Johnny is also impatient, so he wants to harvest as many bubbles as possible on the first day.

Please help Johnny to calculate what is the maximum number of bubbles he can collect on the first day.

## Input Format
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1$$$ $$$\leq$$$ $$$N$$$, $$$M$$$ $$$\leq$$$ $$$N$$$ * $$$M$$$ $$$\leq$$$ $$$10^{5}$$$) - the bubblefield size.

Each of the next $$$N$$$ lines contains $$$M$$$ integers. The $$$j^{th}$$$ element in the $$$i^{th}$$$ line is $$$A_{i,j}$$$ ($$$0$$$ $$$\leq$$$ $$$a_{i,j}$$$ $$$\leq$$$ $$$10^{9}$$$) — the yield of the parcel located in the $$$i^{th}$$$ row and the $$$j^{th}$$$ column.

## Output Format
Output contains one integer number - maximum number of the bubbles Johnny can harvest on the first day.

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

## Note
In the first example, farmer Johnny can harvest all the bubbles by positioning the harvester on the first and the second row.

In the second example, one way Johnny can harvest maximum number of bubbles is to position the harvester in the second row, the fourth row, the second column and the fourth column.

Now solve the problem and return the code.