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

# Problem
You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads!

Initially Zmei Gorynich has $$$x$$$ heads. You can deal $$$n$$$ types of blows. If you deal a blow of the $$$i$$$-th type, you decrease the number of Gorynich's heads by $$$min(d_i, curX)$$$, there $$$curX$$$ is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows $$$h_i$$$ new heads. If $$$curX = 0$$$ then Gorynich is defeated.

You can deal each blow any number of times, in any order.

For example, if $$$curX = 10$$$, $$$d = 7$$$, $$$h = 10$$$ then the number of heads changes to $$$13$$$ (you cut $$$7$$$ heads off, but then Zmei grows $$$10$$$ new ones), but if $$$curX = 10$$$, $$$d = 11$$$, $$$h = 100$$$ then number of heads changes to $$$0$$$ and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer $$$t$$$ independent queries.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) – the number of queries.

The first line of each query contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 100$$$, $$$1 \le x \le 10^9$$$) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following $$$n$$$ lines of each query contain the descriptions of types of blows you can deal. The $$$i$$$-th line contains two integers $$$d_i$$$ and $$$h_i$$$ ($$$1 \le d_i, h_i \le 10^9$$$) — the description of the $$$i$$$-th blow.

## Output Format
For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich.

If Zmei Gorynuch cannot be defeated print $$$-1$$$.

## Examples
```input
3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100
```
```output
2
3
-1
```

## Note
In the first query you can deal the first blow (after that the number of heads changes to $$$10 - 6 + 3 = 7$$$), and then deal the second blow.

In the second query you just deal the first blow three times, and Zmei is defeated.

In third query you can not defeat Zmei Gorynich. Maybe it's better to convince it to stop fighting?

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 a binary string $$$s$$$ (recall that a string is binary if each character is either $$$0$$$ or $$$1$$$).

Let $$$f(t)$$$ be the decimal representation of integer $$$t$$$ written in binary form (possibly with leading zeroes). For example $$$f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$$$ and $$$f(000100) = 4$$$.

The substring $$$s_{l}, s_{l+1}, \dots , s_{r}$$$ is good if $$$r - l + 1 = f(s_l \dots s_r)$$$.

For example string $$$s = 1011$$$ has $$$5$$$ good substrings: $$$s_1 \dots s_1 = 1$$$, $$$s_3 \dots s_3 = 1$$$, $$$s_4 \dots s_4 = 1$$$, $$$s_1 \dots s_2 = 10$$$ and $$$s_2 \dots s_4 = 011$$$.

Your task is to calculate the number of good substrings of string $$$s$$$.

You have to answer $$$t$$$ independent queries.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of queries.

The only line of each query contains string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of only digits $$$0$$$ and $$$1$$$.

It is guaranteed that $$$\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$$$.

## Output Format
For each query print one integer — the number of good substrings of string $$$s$$$.

## Examples
```input
4
0110
0101
00001000
0001000
```
```output
4
3
4
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 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
You are given a directed graph with $$$n$$$ vertices and $$$m$$$ directed edges without self-loops or multiple edges.

Let's denote the $$$k$$$-coloring of a digraph as following: you color each edge in one of $$$k$$$ colors. The $$$k$$$-coloring is good if and only if there no cycle formed by edges of same color.

Find a good $$$k$$$-coloring of given digraph with minimum possible $$$k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 5000$$$, $$$1 \le m \le 5000$$$) — the number of vertices and edges in the digraph, respectively.

Next $$$m$$$ lines contain description of edges — one per line. Each edge is a pair of integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — there is directed edge from $$$u$$$ to $$$v$$$ in the graph.

It is guaranteed that each ordered pair $$$(u, v)$$$ appears in the list of edges at most once.

## Output Format
In the first line print single integer $$$k$$$ — the number of used colors in a good $$$k$$$-coloring of given graph.

In the second line print $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le k$$$), where $$$c_i$$$ is a color of the $$$i$$$-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize $$$k$$$).

## Examples
```input
4 5
1 2
1 3
3 4
2 4
1 4
```
```output
1
1 1 1 1 1
```
-----
```input
3 3
1 2
2 3
3 1
```
```output
2
1 1 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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
Petr stands in line of n people, but he doesn't know exactly which position he occupies. He can say that there are no less than a people standing in front of him and no more than b people standing behind him. Find the number of different positions Petr can occupy.

## Input Format
The only line contains three integers n, a and b (0 ≤ a, b < n ≤ 100).

## Output Format
Print the single number — the number of the sought positions.

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

## Note
The possible positions in the first sample are: 2 and 3 (if we number the positions starting with 1).

In the second sample they are 3, 4 and 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
You are given n k-digit integers. You have to rearrange the digits in the integers so that the difference between the largest and the smallest number was minimum. Digits should be rearranged by the same rule in all integers.

## Input Format
The first line contains integers n and k — the number and digit capacity of numbers correspondingly (1 ≤ n, k ≤ 8). Next n lines contain k-digit positive integers. Leading zeroes are allowed both in the initial integers and the integers resulting from the rearranging of digits.

## Output Format
Print a single number: the minimally possible difference between the largest and the smallest number after the digits are rearranged in all integers by the same rule.

## Examples
```input
6 4
5237
2753
7523
5723
5327
2537
```
```output
2700
```
-----
```input
3 3
010
909
012
```
```output
3
```
-----
```input
7 5
50808
36603
37198
44911
29994
42543
50156
```
```output
20522
```

## Note
In the first sample, if we rearrange the digits in numbers as (3,1,4,2), then the 2-nd and the 4-th numbers will equal 5237 and 2537 correspondingly (they will be maximum and minimum for such order of digits).

In the second sample, if we swap the second digits and the first ones, we get integers 100, 99 and 102.

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
The football season has just ended in Berland. According to the rules of Berland football, each match is played between two teams. The result of each match is either a draw, or a victory of one of the playing teams. If a team wins the match, it gets $$$w$$$ points, and the opposing team gets $$$0$$$ points. If the game results in a draw, both teams get $$$d$$$ points.

The manager of the Berland capital team wants to summarize the results of the season, but, unfortunately, all information about the results of each match is lost. The manager only knows that the team has played $$$n$$$ games and got $$$p$$$ points for them.

You have to determine three integers $$$x$$$, $$$y$$$ and $$$z$$$ — the number of wins, draws and loses of the team. If there are multiple answers, print any of them. If there is no suitable triple $$$(x, y, z)$$$, report about it.

## Input Format
The first line contains four integers $$$n$$$, $$$p$$$, $$$w$$$ and $$$d$$$ $$$(1 \le n \le 10^{12}, 0 \le p \le 10^{17}, 1 \le d < w \le 10^{5})$$$ — the number of games, the number of points the team got, the number of points awarded for winning a match, and the number of points awarded for a draw, respectively. Note that $$$w > d$$$, so the number of points awarded for winning is strictly greater than the number of points awarded for draw.

## Output Format
If there is no answer, print $$$-1$$$.

Otherwise print three non-negative integers $$$x$$$, $$$y$$$ and $$$z$$$ — the number of wins, draws and losses of the team. If there are multiple possible triples $$$(x, y, z)$$$, print any of them. The numbers should meet the following conditions:

- $$$x \cdot w + y \cdot d = p$$$,
- $$$x + y + z = n$$$.

## Examples
```input
30 60 3 1
```
```output
17 9 4
```
-----
```input
10 51 5 4
```
```output
-1
```
-----
```input
20 0 15 5
```
```output
0 0 20
```

## Note
One of the possible answers in the first example — $$$17$$$ wins, $$$9$$$ draws and $$$4$$$ losses. Then the team got $$$17 \cdot 3 + 9 \cdot 1 = 60$$$ points in $$$17 + 9 + 4 = 30$$$ games.

In the second example the maximum possible score is $$$10 \cdot 5 = 50$$$. Since $$$p = 51$$$, there is no answer.

In the third example the team got $$$0$$$ points, so all $$$20$$$ games were lost.

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
You are given a sequence $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ integers.

You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.

Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $$$k$$$ times.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$$$ — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{9})$$$.

## Output Format
Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $$$k$$$ times.

## Examples
```input
4 5
3 1 7 5
```
```output
2
```
-----
```input
3 10
100 100 100
```
```output
0
```
-----
```input
10 9
4 5 5 7 5 4 5 2 4 3
```
```output
1
```

## Note
In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes $$$[3, 3, 5, 5]$$$, and the difference between maximum and minimum is $$$2$$$. You still can perform one operation after that, but it's useless since you can't make the answer less than $$$2$$$.

In the second example all elements are already equal, so you may get $$$0$$$ as the answer even without applying any operations.

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

# Problem
A sequence $$$a = [a_1, a_2, \ldots, a_l]$$$ of length $$$l$$$ has an ascent if there exists a pair of indices $$$(i, j)$$$ such that $$$1 \le i < j \le l$$$ and $$$a_i < a_j$$$. For example, the sequence $$$[0, 2, 0, 2, 0]$$$ has an ascent because of the pair $$$(1, 4)$$$, but the sequence $$$[4, 3, 3, 3, 1]$$$ doesn't have an ascent.

Let's call a concatenation of sequences $$$p$$$ and $$$q$$$ the sequence that is obtained by writing down sequences $$$p$$$ and $$$q$$$ one right after another without changing the order. For example, the concatenation of the $$$[0, 2, 0, 2, 0]$$$ and $$$[4, 3, 3, 3, 1]$$$ is the sequence $$$[0, 2, 0, 2, 0, 4, 3, 3, 3, 1]$$$. The concatenation of sequences $$$p$$$ and $$$q$$$ is denoted as $$$p+q$$$.

Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has $$$n$$$ sequences $$$s_1, s_2, \ldots, s_n$$$ which may have different lengths.

Gyeonggeun will consider all $$$n^2$$$ pairs of sequences $$$s_x$$$ and $$$s_y$$$ ($$$1 \le x, y \le n$$$), and will check if its concatenation $$$s_x + s_y$$$ has an ascent. Note that he may select the same sequence twice, and the order of selection matters.

Please count the number of pairs ($$$x, y$$$) of sequences $$$s_1, s_2, \ldots, s_n$$$ whose concatenation $$$s_x + s_y$$$ contains an ascent.

## Input Format
The first line contains the number $$$n$$$ ($$$1 \le n \le 100\,000$$$) denoting the number of sequences.

The next $$$n$$$ lines contain the number $$$l_i$$$ ($$$1 \le l_i$$$) denoting the length of $$$s_i$$$, followed by $$$l_i$$$ integers $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i}$$$ ($$$0 \le s_{i, j} \le 10^6$$$) denoting the sequence $$$s_i$$$.

It is guaranteed that the sum of all $$$l_i$$$ does not exceed $$$100\,000$$$.

## Output Format
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

## Examples
```input
5
1 1
1 1
1 2
1 4
1 3
```
```output
9
```
-----
```input
3
4 2 0 2 0
6 9 9 8 8 7 7
1 6
```
```output
7
```
-----
```input
10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100
```
```output
72
```

## Note
For the first example, the following $$$9$$$ arrays have an ascent: $$$[1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4]$$$. Arrays with the same contents are counted as their occurences.

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

You are also given a set of distinct positions $$$p_1, p_2, \dots, p_m$$$, where $$$1 \le p_i < n$$$. The position $$$p_i$$$ means that you can swap elements $$$a[p_i]$$$ and $$$a[p_i + 1]$$$. You can apply this operation any number of times for each of the given positions.

Your task is to determine if it is possible to sort the initial array in non-decreasing order ($$$a_1 \le a_2 \le \dots \le a_n$$$) using only allowed swaps.

For example, if $$$a = [3, 2, 1]$$$ and $$$p = [1, 2]$$$, then we can first swap elements $$$a[2]$$$ and $$$a[3]$$$ (because position $$$2$$$ is contained in the given set $$$p$$$). We get the array $$$a = [3, 1, 2]$$$. Then we swap $$$a[1]$$$ and $$$a[2]$$$ (position $$$1$$$ is also contained in $$$p$$$). We get the array $$$a = [1, 3, 2]$$$. Finally, we swap $$$a[2]$$$ and $$$a[3]$$$ again and get the array $$$a = [1, 2, 3]$$$, sorted in non-decreasing order.

You can see that if $$$a = [4, 1, 2, 3]$$$ and $$$p = [3, 2]$$$ then you cannot sort the array.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Then $$$t$$$ test cases follow. The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m < n \le 100$$$) — the number of elements in $$$a$$$ and the number of elements in $$$p$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$). The third line of the test case contains $$$m$$$ integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i < n$$$, all $$$p_i$$$ are distinct) — the set of positions described in the problem statement.

## Output Format
For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order ($$$a_1 \le a_2 \le \dots \le a_n$$$) using only allowed swaps. Otherwise, print "NO".

## Examples
```input
6
3 2
3 2 1
1 2
4 2
4 1 2 3
3 2
5 1
1 2 3 4 5
1
4 2
2 1 4 3
1 3
4 2
4 3 2 1
1 3
5 2
2 1 2 3 3
1 4
```
```output
YES
NO
YES
YES
NO
YES
```

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
You are given three integers $$$a \le b \le c$$$.

In one move, you can add $$$+1$$$ or $$$-1$$$ to any of these integers (i.e. increase or decrease any number by one). You can perform such operation any (possibly, zero) number of times, you can even perform this operation several times with one number. Note that you cannot make non-positive numbers using such operations.

You have to perform the minimum number of such operations in order to obtain three integers $$$A \le B \le C$$$ such that $$$B$$$ is divisible by $$$A$$$ and $$$C$$$ is divisible by $$$B$$$.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The next $$$t$$$ lines describe test cases. Each test case is given on a separate line as three space-separated integers $$$a, b$$$ and $$$c$$$ ($$$1 \le a \le b \le c \le 10^4$$$).

## Output Format
For each test case, print the answer. In the first line print $$$res$$$ — the minimum number of operations you have to perform to obtain three integers $$$A \le B \le C$$$ such that $$$B$$$ is divisible by $$$A$$$ and $$$C$$$ is divisible by $$$B$$$. On the second line print any suitable triple $$$A, B$$$ and $$$C$$$.

## Examples
```input
8
1 2 3
123 321 456
5 10 15
15 18 21
100 100 101
1 22 29
3 19 38
6 30 46
```
```output
1
1 1 3
102
114 228 456
4
4 8 16
6
18 18 18
1
100 100 100
7
1 22 22
2
1 19 38
8
6 24 48
```

Now solve the problem and return the code.