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

# Problem
Polycarp has $$$n$$$ wheels and a car with $$$m$$$ slots for wheels. The initial pressure in the $$$i$$$-th wheel is $$$a_i$$$.

Polycarp's goal is to take exactly $$$m$$$ wheels among the given $$$n$$$ wheels and equalize the pressure in them (then he can put these wheels in a car and use it for driving). In one minute he can decrease or increase the pressure in any (single) wheel by $$$1$$$. He can increase the pressure no more than $$$k$$$ times in total because it is hard to pump up wheels.

Help Polycarp and say what is the minimum number of minutes he needs to spend to equalize the pressure of at least $$$m$$$ wheels among the given $$$n$$$ wheels.

## Input Format
The first line of the input contains three integers $$$n, m$$$ and $$$k$$$ ($$$1 \le m \le n \le 2 \cdot 10^5, 0 \le k \le 10^9$$$) — the number of wheels, the number of slots for wheels in a car and the number of times Polycarp can increase by $$$1$$$ the pressure in a wheel.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the pressure in the $$$i$$$-th wheel.

## Output Format
Print one integer — the minimum number of minutes Polycarp needs to spend to equalize the pressure in at least $$$m$$$ wheels among the given $$$n$$$ wheels.

## Examples
```input
6 6 7
6 15 16 20 1 5
```
```output
39
```
-----
```input
6 3 1
4 8 15 16 23 42
```
```output
8
```
-----
```input
5 4 0
5 5 5 4 5
```
```output
0
```

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

# Problem
You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges.

Recall that a cycle is a path that starts and ends in the same vertex. A cycle in a graph is called simple if it contains each vertex (except the starting and ending one) no more than once (the starting and the ending one is contained always twice). Note that loops are considered to be simple cycles.

In one move you can choose any simple cycle in this graph and erase the edges corresponding to this cycle (corresponding vertices remain in the graph). It is allowed to erase the loop or two copies of the same edge (take a look at examples).

Your problem is to apply some sequence of moves to obtain the graph without edges. It is not necessary to minimize the number of cycles. If it is impossible, print "NO".

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges in the graph.

The next $$$m$$$ lines contain edges of the graph. The $$$i$$$-th line contains the $$$i$$$-th edge $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le n$$$), where $$$x_i$$$ and $$$y_i$$$ are vertices connected by the $$$i$$$-th edge. The graph can contain loops or multiple edges.

## Output Format
If it is impossible to decompose the given graph into simple cycles, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print $$$k$$$ — the number of simple cycles in the graph decomposition.

In the next $$$k$$$ lines print cycles themselves. The $$$j$$$-th line should contain the $$$j$$$-th cycle. First, print $$$c_j$$$ — the number of vertices in the $$$j$$$-th cycle. Then print the cycle as a sequence of vertices. All neighbouring (adjacent) vertices in the printed path should be connected by an edge that isn't contained in other cycles.

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

## Note
The picture corresponding to 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 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given the sequence $$$a_1, a_2, \dots, a_n$$$. You can choose any subset of elements and then reorder them to create a "saw".

The sequence $$$b_1, b_2, \dots, b_m$$$ is called a "saw" if the elements satisfy one of the following series of inequalities: $$$b_1>b_2<b_3>b_4<\dots$$$ or $$$b_1<b_2>b_3<b_4>\dots$$$.

Find the longest saw which can be obtained from a given array.

Note that both the given sequence $$$a$$$ and the required saw $$$b$$$ can contain duplicated (non-unique) values.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases in the input. Then the descriptions of the $$$t$$$ test cases follow. Each test case begins with a line containing integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$). Then a line containing $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) follows.

It's guaranteed that $$$\sum{n}$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print two lines: print the length of the longest saw in the first line, and the saw itself in the second line. If there are several solutions, print any of them.

## Examples
```input
3
10
10 9 8 7 6 5 4 3 2 1
7
1 2 2 2 3 2 2
3
100 100 100
```
```output
10
1 6 2 7 3 8 4 9 5 10 
4
2 1 3 2 
1
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: 6.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ segments on the $$$Ox$$$ axis. The $$$i$$$-th segment is given as a pair $$$l_i, r_i$$$, where $$$l_i$$$ is the position of the left end of the $$$i$$$-th segment and $$$r_i$$$ is the position of the right end of the $$$i$$$-th segment. Segments may intersect, overlap, or even coincide. A segment is a set of numbers (including floating-point numbers) lying between the segment ends or coinciding with them. Formally, the segment $$$[l, r]=\{x~|~x \in \Bbb{R},~l \le x \le r\}$$$.

Let the union of segments be the set of all axis points covered by the set of segments. Let's call a subset of the given segments good if its union equals the union of all $$$n$$$ segments.

Your task is to calculate the number of good subsets of the given $$$n$$$ segments. Since the answer may be very large, print it modulo $$$998244353$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of segments.

The next $$$n$$$ lines contain segments. The $$$i$$$-th segment is given as a pair $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$), where $$$l_i$$$ is the left border of the segment and $$$r_i$$$ is the right border of the segment. Segments may intersect, overlap, or even coincide.

## Output Format
Print the number of good subsets of the given set of segments. Since the answer may be very large, print it modulo $$$998244353$$$.

## Examples
```input
3
1 1
2 6
1 6
```
```output
4
```
-----
```input
2
3 4
2 5
```
```output
2
```
-----
```input
4
1 2
5 5
2 3
1 3
```
```output
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: 512.0 MB

# Problem
Soon after the Chunga-Changa island was discovered, it started to acquire some forms of civilization and even market economy. A new currency arose, colloquially called "chizhik". One has to pay in chizhiks to buy a coconut now.

Sasha and Masha are about to buy some coconuts which are sold at price $$$z$$$ chizhiks per coconut. Sasha has $$$x$$$ chizhiks, Masha has $$$y$$$ chizhiks. Each girl will buy as many coconuts as she can using only her money. This way each girl will buy an integer non-negative number of coconuts.

The girls discussed their plans and found that the total number of coconuts they buy can increase (or decrease) if one of them gives several chizhiks to the other girl. The chizhiks can't be split in parts, so the girls can only exchange with integer number of chizhiks.

Consider the following example. Suppose Sasha has $$$5$$$ chizhiks, Masha has $$$4$$$ chizhiks, and the price for one coconut be $$$3$$$ chizhiks. If the girls don't exchange with chizhiks, they will buy $$$1 + 1 = 2$$$ coconuts. However, if, for example, Masha gives Sasha one chizhik, then Sasha will have $$$6$$$ chizhiks, Masha will have $$$3$$$ chizhiks, and the girls will buy $$$2 + 1 = 3$$$ coconuts.

It is not that easy to live on the island now, so Sasha and Mash want to exchange with chizhiks in such a way that they will buy the maximum possible number of coconuts. Nobody wants to have a debt, so among all possible ways to buy the maximum possible number of coconuts find such a way that minimizes the number of chizhiks one girl gives to the other (it is not important who will be the person giving the chizhiks).

## Input Format
The first line contains three integers $$$x$$$, $$$y$$$ and $$$z$$$ ($$$0 \le x, y \le 10^{18}$$$, $$$1 \le z \le 10^{18}$$$) — the number of chizhics Sasha has, the number of chizhics Masha has and the price of a coconut.

## Output Format
Print two integers: the maximum possible number of coconuts the girls can buy and the minimum number of chizhiks one girl has to give to the other.

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

## Note
The first example is described in the statement. In the second example the optimal solution is to dot exchange any chizhiks. The girls will buy $$$3 + 4 = 7$$$ coconuts.

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: 512.0 MB

# Problem
Dima worked all day and wrote down on a long paper strip his favorite number $$$n$$$ consisting of $$$l$$$ digits. Unfortunately, the strip turned out to be so long that it didn't fit in the Dima's bookshelf.

To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a positive integer without leading zeros. After that he will compute the sum of the two integers and write it down on a new strip.

Dima wants the resulting integer to be as small as possible, because it increases the chances that the sum will fit it in the bookshelf. Help Dima decide what is the minimum sum he can obtain.

## Input Format
The first line contains a single integer $$$l$$$ ($$$2 \le l \le 100\,000$$$) — the length of the Dima's favorite number.

The second line contains the positive integer $$$n$$$ initially written on the strip: the Dima's favorite number.

The integer $$$n$$$ consists of exactly $$$l$$$ digits and it does not contain leading zeros. Dima guarantees, that there is at least one valid way to split the strip.

## Output Format
Print a single integer — the smallest number Dima can obtain.

## Examples
```input
7
1234567
```
```output
1801
```
-----
```input
3
101
```
```output
11
```

## Note
In the first example Dima can split the number $$$1234567$$$ into integers $$$1234$$$ and $$$567$$$. Their sum is $$$1801$$$.

In the second example Dima can split the number $$$101$$$ into integers $$$10$$$ and $$$1$$$. Their sum is $$$11$$$. Note that it is impossible to split the strip into "1" and "01" since the numbers can't start with zeros.

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: 512.0 MB

# Problem
Innokenty works at a flea market and sells some random stuff rare items. Recently he found an old rectangular blanket. It turned out that the blanket is split in $$$n \cdot m$$$ colored pieces that form a rectangle with $$$n$$$ rows and $$$m$$$ columns.

The colored pieces attracted Innokenty's attention so he immediately came up with the following business plan. If he cuts out a subrectangle consisting of three colored stripes, he can sell it as a flag of some country. Innokenty decided that a subrectangle is similar enough to a flag of some country if it consists of three stripes of equal heights placed one above another, where each stripe consists of cells of equal color. Of course, the color of the top stripe must be different from the color of the middle stripe; and the color of the middle stripe must be different from the color of the bottom stripe.

Innokenty has not yet decided what part he will cut out, but he is sure that the flag's boundaries should go along grid lines. Also, Innokenty won't rotate the blanket. Please help Innokenty and count the number of different subrectangles Innokenty can cut out and sell as a flag. Two subrectangles located in different places but forming the same flag are still considered different.

These subrectangles are flags.

These subrectangles are not flags.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1\,000$$$) — the number of rows and the number of columns on the blanket.

Each of the next $$$n$$$ lines contains $$$m$$$ lowercase English letters from 'a' to 'z' and describes a row of the blanket. Equal letters correspond to equal colors, different letters correspond to different colors.

## Output Format
In the only line print the number of subrectangles which form valid flags.

## Examples
```input
4 3
aaa
bbb
ccb
ddd
```
```output
6
```
-----
```input
6 1
a
a
b
b
c
c
```
```output
1
```

## Note
The selected subrectangles are flags 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 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.5 seconds
Memory limit: 512.0 MB

# Problem
Misha was interested in water delivery from childhood. That's why his mother sent him to the annual Innovative Olympiad in Irrigation (IOI). Pupils from all Berland compete there demonstrating their skills in watering. It is extremely expensive to host such an olympiad, so after the first $$$n$$$ olympiads the organizers introduced the following rule of the host city selection.

The host cities of the olympiads are selected in the following way. There are $$$m$$$ cities in Berland wishing to host the olympiad, they are numbered from $$$1$$$ to $$$m$$$. The host city of each next olympiad is determined as the city that hosted the olympiad the smallest number of times before. If there are several such cities, the city with the smallest index is selected among them.

Misha's mother is interested where the olympiad will be held in some specific years. The only information she knows is the above selection rule and the host cities of the first $$$n$$$ olympiads. Help her and if you succeed, she will ask Misha to avoid flooding your house.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \leq n, m, q \leq 500\,000$$$) — the number of olympiads before the rule was introduced, the number of cities in Berland wishing to host the olympiad, and the number of years Misha's mother is interested in, respectively.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq m$$$), where $$$a_i$$$ denotes the city which hosted the olympiad in the $$$i$$$-th year. Note that before the rule was introduced the host city was chosen arbitrarily.

Each of the next $$$q$$$ lines contains an integer $$$k_i$$$ ($$$n + 1 \leq k_i \leq 10^{18}$$$) — the year number Misha's mother is interested in host city in.

## Output Format
Print $$$q$$$ integers. The $$$i$$$-th of them should be the city the olympiad will be hosted in the year $$$k_i$$$.

## Examples
```input
6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16
```
```output
4
3
4
2
3
4
1
2
3
4
```
-----
```input
4 5 4
4 4 5 1
15
9
13
6
```
```output
5
3
3
3
```

## Note
In the first example Misha's mother is interested in the first $$$10$$$ years after the rule was introduced. The host cities these years are 4, 3, 4, 2, 3, 4, 1, 2, 3, 4.

In the second example the host cities after the new city is introduced are 2, 3, 1, 2, 3, 5, 1, 2, 3, 4, 5, 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 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: 512.0 MB

# Problem
This problem differs from the next problem only in constraints.

Petya decided to visit Byteland during the summer holidays. It turned out that the history of this country is quite unusual.

Initially, there were $$$n$$$ different countries on the land that is now Berland. Each country had its own territory that was represented as a rectangle on the map. The sides of the rectangle were parallel to the axes, and the corners were located at points with integer coordinates. Territories of no two countries intersected, but it was possible that some territories touched each other. As time passed, sometimes two countries merged into one. It only happened if the union of their territories was also a rectangle. In the end only one country remained — Byteland.

Initially, each country had a rectangular castle inside its territory. Its sides were parallel to the axes and its corners had integer coordinates. Some castles might touch the border of the corresponding country and sides or other castles. Miraculously, after all the unions the castles are still intact. Unfortunately, their locations are the only information we have to restore the initial territories of the countries.

The possible formation of Byteland. The castles are shown in blue.

Petya wonders why no information about the initial countries remained. He suspected that the whole story is a fake. You were recommended to him as a smart person. Please check whether or not there exists a possible set of initial territories that could make the story true.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of countries and castles.

Each of the next $$$n$$$ lines contains four integers $$$a_i, b_i, c_i, d_i$$$ ($$$0 \leq a_i < c_i \leq 10^9$$$, $$$0 \leq b_i < d_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th castle, where $$$(a_i, b_i)$$$ are the coordinates of the lower left corner and $$$(c_i, d_i)$$$ are the coordinates of the upper right corner.

It is guaranteed, that no two castles intersect, however, they may touch.

## Output Format
If there exists a possible set of territories that satisfies the story, print "YES", otherwise print "NO".

You can print each letter in any case (upper or lower).

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

## Note
The castles in the first and second examples are shown on the pictures below.

Now solve the problem and return the code.