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

# Problem
Bob watches TV every day. He always sets the volume of his TV to $$$b$$$. However, today he is angry to find out someone has changed the volume to $$$a$$$. Of course, Bob has a remote control that can change the volume.

There are six buttons ($$$-5, -2, -1, +1, +2, +5$$$) on the control, which in one press can either increase or decrease the current volume by $$$1$$$, $$$2$$$, or $$$5$$$. The volume can be arbitrarily large, but can never be negative. In other words, Bob cannot press the button if it causes the volume to be lower than $$$0$$$.

As Bob is so angry, he wants to change the volume to $$$b$$$ using as few button presses as possible. However, he forgets how to do such simple calculations, so he asks you for help. Write a program that given $$$a$$$ and $$$b$$$, finds the minimum number of presses to change the TV volume from $$$a$$$ to $$$b$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 1\,000$$$). Then the descriptions of the test cases follow.

Each test case consists of one line containing two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 10^{9}$$$) — the current volume and Bob's desired volume, respectively.

## Output Format
For each test case, output a single integer — the minimum number of presses to change the TV volume from $$$a$$$ to $$$b$$$. If Bob does not need to change the volume (i.e. $$$a=b$$$), then print $$$0$$$.

## Examples
```input
3
4 0
5 14
3 9
```
```output
2
3
2
```

## Note
In the first example, Bob can press the $$$-2$$$ button twice to reach $$$0$$$. Note that Bob can not press $$$-5$$$ when the volume is $$$4$$$ since it will make the volume negative.

In the second example, one of the optimal ways for Bob is to press the $$$+5$$$ twice, then press $$$-1$$$ once.

In the last example, Bob can press the $$$+5$$$ once, then press $$$+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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are organizing a boxing tournament, where $$$n$$$ boxers will participate ($$$n$$$ is a power of $$$2$$$), and your friend is one of them. All boxers have different strength from $$$1$$$ to $$$n$$$, and boxer $$$i$$$ wins in the match against boxer $$$j$$$ if and only if $$$i$$$ is stronger than $$$j$$$.

The tournament will be organized as follows: $$$n$$$ boxers will be divided into pairs; the loser in each pair leaves the tournament, and $$$\frac{n}{2}$$$ winners advance to the next stage, where they are divided into pairs again, and the winners in all pairs advance to the next stage, and so on, until only one boxer remains (who is declared the winner).

Your friend really wants to win the tournament, but he may be not the strongest boxer. To help your friend win the tournament, you may bribe his opponents: if your friend is fighting with a boxer you have bribed, your friend wins even if his strength is lower.

Furthermore, during each stage you distribute the boxers into pairs as you wish.

The boxer with strength $$$i$$$ can be bribed if you pay him $$$a_i$$$ dollars. What is the minimum number of dollars you have to spend to make your friend win the tournament, provided that you arrange the boxers into pairs during each stage as you wish?

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2^{18}$$$) — the number of boxers. $$$n$$$ is a power of $$$2$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, where $$$a_i$$$ is the number of dollars you have to pay if you want to bribe the boxer with strength $$$i$$$. Exactly one of $$$a_i$$$ is equal to $$$-1$$$ — it means that the boxer with strength $$$i$$$ is your friend. All other values are in the range $$$[1, 10^9]$$$.

## Output Format
Print one integer — the minimum number of dollars you have to pay so your friend wins.

## Examples
```input
4
3 9 1 -1
```
```output
0
```
-----
```input
8
11 -1 13 19 24 7 17 5
```
```output
12
```

## Note
In the first test case no matter how you will distribute boxers into pairs, your friend is the strongest boxer and anyway wins the tournament.

In the second test case you can distribute boxers as follows (your friend is number $$$2$$$):

$$$1 : 2, 8 : 5, 7 : 3, 6 : 4$$$ (boxers $$$2, 8, 7$$$ and $$$6$$$ advance to the next stage);

$$$2 : 6, 8 : 7$$$ (boxers $$$2$$$ and $$$8$$$ advance to the next stage, you have to bribe the boxer with strength $$$6$$$);

$$$2 : 8$$$ (you have to bribe the boxer with strength $$$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 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.5 seconds
Memory limit: 256.0 MB

# Problem
You're given a tree with $$$n$$$ vertices. The color of the $$$i$$$-th vertex is $$$h_{i}$$$.

The value of the tree is defined as $$$\sum\limits_{h_{i} = h_{j}, 1 \le i < j \le n}{dis(i,j)}$$$, where $$$dis(i,j)$$$ is the number of edges on the shortest path between $$$i$$$ and $$$j$$$.

The color of each vertex is lost, you only remember that $$$h_{i}$$$ can be any integer from $$$[l_{i}, r_{i}]$$$(inclusive). You want to calculate the sum of values of all trees meeting these conditions modulo $$$10^9 + 7$$$ (the set of edges is fixed, but each color is unknown, so there are $$$\prod\limits_{i = 1}^{n} (r_{i} - l_{i} + 1)$$$ different trees).

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

Then $$$n$$$ lines follow, each line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^5$$$) denoting the range of possible colors of vertex $$$i$$$.

Then $$$n - 1$$$ lines follow, each containing two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) denoting an edge of the tree. It is guaranteed that these edges form a tree.

## Output Format
Print one integer — the sum of values of all possible trees, taken modulo $$$10^9 + 7$$$.

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

## Note
In the first example there are four different ways to color the tree (so, there are four different trees):

- a tree with vertices colored as follows: $$$\lbrace 1,1,1,1 \rbrace$$$. The value of this tree is $$$dis(1,2)+dis(1,3)+dis(1,4)+dis(2,3)+dis(2,4)+dis(3,4) = 10$$$;
- a tree with vertices colored as follows: $$$\lbrace 1,2,1,1 \rbrace$$$. The value of this tree is $$$dis(1,3)+dis(1,4)+dis(3,4)=4$$$;
- a tree with vertices colored as follows: $$$\lbrace 1,1,1,2 \rbrace$$$. The value of this tree is $$$dis(1,2)+dis(1,3)+dis(2,3)=4$$$;
- a tree with vertices colored as follows: $$$\lbrace 1,2,1,2 \rbrace$$$. The value of this tree is $$$dis(1,3)+dis(2,4)=4$$$.

Overall the sum of all values is $$$10+4+4+4=22$$$.

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
This is the hard version of this problem. The only difference is the limit of $$$n$$$ - the length of the input string. In this version, $$$1 \leq n \leq 10^6$$$.

Let's define a correct bracket sequence and its depth as follow:

- An empty string is a correct bracket sequence with depth $$$0$$$.
- If "s" is a correct bracket sequence with depth $$$d$$$ then "(s)" is a correct bracket sequence with depth $$$d + 1$$$.
- If "s" and "t" are both correct bracket sequences then their concatenation "st" is a correct bracket sequence with depth equal to the maximum depth of $$$s$$$ and $$$t$$$.

For a (not necessarily correct) bracket sequence $$$s$$$, we define its depth as the maximum depth of any correct bracket sequence induced by removing some characters from $$$s$$$ (possibly zero). For example: the bracket sequence $$$s = $$$"())(())" has depth $$$2$$$, because by removing the third character we obtain a correct bracket sequence "()(())" with depth $$$2$$$.

Given a string $$$a$$$ consists of only characters '(', ')' and '?'. Consider all (not necessarily correct) bracket sequences obtained by replacing all characters '?' in $$$a$$$ by either '(' or ')'. Calculate the sum of all the depths of all these bracket sequences. As this number can be large, find it modulo $$$998244353$$$.

Hacks in this problem can be done only if easy and hard versions of this problem was solved.

## Input Format
The only line contains a non-empty string consist of only '(', ')' and '?'. The length of the string is at most $$$10^6$$$.

## Output Format
Print the answer modulo $$$998244353$$$ in a single line.

## Examples
```input
??
```
```output
1
```
-----
```input
(?(?))
```
```output
9
```

## Note
In the first test case, we can obtain $$$4$$$ bracket sequences by replacing all characters '?' with either '(' or ')':

- "((". Its depth is $$$0$$$;
- "))". Its depth is $$$0$$$;
- ")(". Its depth is $$$0$$$;
- "()". Its depth is $$$1$$$.

So, the answer is $$$1 = 0 + 0 + 0 + 1$$$.

In the second test case, we can obtain $$$4$$$ bracket sequences by replacing all characters '?' with either '(' or ')':

- "(((())". Its depth is $$$2$$$;
- "()()))". Its depth is $$$2$$$;
- "((()))". Its depth is $$$3$$$;
- "()(())". Its depth is $$$2$$$.

So, the answer is $$$9 = 2 + 2 + 3 + 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
New Year is coming! Vasya has prepared a New Year's verse and wants to recite it in front of Santa Claus.

Vasya's verse contains $$$n$$$ parts. It takes $$$a_i$$$ seconds to recite the $$$i$$$-th part. Vasya can't change the order of parts in the verse: firstly he recites the part which takes $$$a_1$$$ seconds, secondly — the part which takes $$$a_2$$$ seconds, and so on. After reciting the verse, Vasya will get the number of presents equal to the number of parts he fully recited.

Vasya can skip at most one part of the verse while reciting it (if he skips more than one part, then Santa will definitely notice it).

Santa will listen to Vasya's verse for no more than $$$s$$$ seconds. For example, if $$$s = 10$$$, $$$a = [100, 9, 1, 1]$$$, and Vasya skips the first part of verse, then he gets two presents.

Note that it is possible to recite the whole verse (if there is enough time).

Determine which part Vasya needs to skip to obtain the maximum possible number of gifts. If Vasya shouldn't skip anything, print 0. If there are multiple answers, print any of them.

You have to process $$$t$$$ test cases.

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

The first line of each test case contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 10^5, 1 \le s \le 10^9$$$) — the number of parts in the verse and the maximum number of seconds Santa will listen to Vasya, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the time it takes to recite each part of the verse.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print one integer — the number of the part that Vasya needs to skip to obtain the maximum number of gifts. If Vasya shouldn't skip any parts, print 0.

## Examples
```input
3
7 11
2 9 1 3 18 1 4
4 35
11 9 10 7
1 8
5
```
```output
2
1
0
```

## Note
In the first test case if Vasya skips the second part then he gets three gifts.

In the second test case no matter what part of the verse Vasya skips.

In the third test case Vasya can recite the whole verse.

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
New Year is getting near. So it's time to change handles on codeforces. Mishka wants to change his handle but in such a way that people would not forget who he is.

To make it work, he only allowed to change letters case. More formally, during one handle change he can choose any segment of his handle $$$[i; i + l - 1]$$$ and apply tolower or toupper to all letters of his handle on this segment (more fomally, replace all uppercase letters with corresponding lowercase or vice versa). The length $$$l$$$ is fixed for all changes.

Because it is not allowed to change codeforces handle too often, Mishka can perform at most $$$k$$$ such operations. What is the minimum value of $$$min(lower, upper)$$$ (where $$$lower$$$ is the number of lowercase letters, and $$$upper$$$ is the number of uppercase letters) can be obtained after optimal sequence of changes?

## Input Format
The first line of the input contains three integers $$$n, k$$$ and $$$l$$$ ($$$1 \le n, k, l \le 10^6, l \le n)$$$ — the length of Mishka's handle, the number of changes and the length of the segment.

The second line of the input contains one string $$$s$$$, consisting of $$$n$$$ lowercase and uppercase Latin letters — Mishka's handle.

## Output Format
Print one integer — the minimum value of $$$min(lower, upper)$$$ after that Mishka change his handle at most $$$k$$$ times in a way described in the problem statement.

## Examples
```input
7 1 4
PikMike
```
```output
0
```
-----
```input
15 2 2
AaAaAAaaAAAAaaA
```
```output
2
```
-----
```input
14 2 6
aBcdEFGHIJklMn
```
```output
0
```
-----
```input
9 2 2
aAaAAAaaA
```
```output
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
One day Anna got the following task at school: to arrange several numbers in a circle so that any two neighboring numbers differs exactly by 1. Anna was given several numbers and arranged them in a circle to fulfill the task. Then she wanted to check if she had arranged the numbers correctly, but at this point her younger sister Maria came and shuffled all numbers. Anna got sick with anger but what's done is done and the results of her work had been destroyed. But please tell Anna: could she have hypothetically completed the task using all those given numbers?

## Input Format
The first line contains an integer n — how many numbers Anna had (3 ≤ n ≤ 105). The next line contains those numbers, separated by a space. All numbers are integers and belong to the range from 1 to 109.

## Output Format
Print the single line "YES" (without the quotes), if Anna could have completed the task correctly using all those numbers (using all of them is necessary). If Anna couldn't have fulfilled the task, no matter how hard she would try, print "NO" (without the quotes).

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

# Problem
Anna's got a birthday today. She invited many guests and cooked a huge (nearly infinite) birthday cake decorated by n banana circles of different sizes. Maria's birthday is about to start in 7 minutes too, and while Anna is older, she decided to play the boss a little. She told Maria to cut the cake by k straight-line cuts (the cutting lines can intersect) to divide banana circles into banana pieces.

Anna has many guests and she wants everyone to get at least one banana piece. That's why she told Maria to make the total number of banana pieces maximum. It's not a problem if some banana pieces end up on the same cake piece — the key is to make the maximum number of banana pieces. Determine what result Maria will achieve.

## Input Format
The first line contains two integers n and k — the number of banana circles and the number of cuts Maria should perform (1 ≤ n ≤ 1000, 1 ≤ k ≤ 105). Next n lines contain the positions and sizes of the banana circles (all banana circles are round). On the cake the Cartesian coordinate system is defined. Each line contains three integers x, y and r — the coordinates of the center of the corresponding banana piece and its radius ( - 1000 ≤ x, y ≤ 1000, 1 ≤ r ≤ 1000).

It is guaranteed that the banana circles do not intersect, do not touch each other and do not overlap with each other.

Pretest 10 is big test with n = k = 1000.

## Output Format
Print the only integer — the largest number of banana pieces that Maria can get after she performs the k straight-line cuts.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

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

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

# Problem
You are given $$$n$$$ pairwise non-collinear two-dimensional vectors. You can make shapes in the two-dimensional plane with these vectors in the following fashion:

1. Start at the origin $$$(0, 0)$$$.
2. Choose a vector and add the segment of the vector to the current point. For example, if your current point is at $$$(x, y)$$$ and you choose the vector $$$(u, v)$$$, draw a segment from your current point to the point at $$$(x + u, y + v)$$$ and set your current point to $$$(x + u, y + v)$$$.
3. Repeat step 2 until you reach the origin again.

You can reuse a vector as many times as you want.

Count the number of different, non-degenerate (with an area greater than $$$0$$$) and convex shapes made from applying the steps, such that the shape can be contained within a $$$m \times m$$$ square, and the vectors building the shape are in counter-clockwise fashion. Since this number can be too large, you should calculate it by modulo $$$998244353$$$.

Two shapes are considered the same if there exists some parallel translation of the first shape to another.

A shape can be contained within a $$$m \times m$$$ square if there exists some parallel translation of this shape so that every point $$$(u, v)$$$ inside or on the border of the shape satisfies $$$0 \leq u, v \leq m$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$  — the number of vectors and the size of the square ($$$1 \leq n \leq 5$$$, $$$1 \leq m \leq 10^9$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$  — the $$$x$$$-coordinate and $$$y$$$-coordinate of the $$$i$$$-th vector ($$$|x_i|, |y_i| \leq 4$$$, $$$(x_i, y_i) \neq (0, 0)$$$).

It is guaranteed, that no two vectors are parallel, so for any two indices $$$i$$$ and $$$j$$$ such that $$$1 \leq i < j \leq n$$$, there is no real value $$$k$$$ such that $$$x_i \cdot k = x_j$$$ and $$$y_i \cdot k = y_j$$$.

## Output Format
Output a single integer  — the number of satisfiable shapes by modulo $$$998244353$$$.

## Examples
```input
3 3
-1 0
1 1
0 -1
```
```output
3
```
-----
```input
3 3
-1 0
2 2
0 -1
```
```output
1
```
-----
```input
3 1776966
-1 0
3 3
0 -2
```
```output
296161
```
-----
```input
4 15
-4 -4
-1 1
-1 -4
4 3
```
```output
1
```
-----
```input
5 10
3 -4
4 -3
1 -3
2 -3
-3 -4
```
```output
0
```
-----
```input
5 1000000000
-2 4
2 -3
0 -4
2 4
-1 -3
```
```output
9248783
```

## Note
The shapes for the first sample are:

The only shape for the second sample is:

The only shape for the fourth sample is:

Now solve the problem and return the code.