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

# Problem
DLS and JLS are bored with a Math lesson. In order to entertain themselves, DLS took a sheet of paper and drew $$$n$$$ distinct lines, given by equations $$$y = x + p_i$$$ for some distinct $$$p_1, p_2, \ldots, p_n$$$.

Then JLS drew on the same paper sheet $$$m$$$ distinct lines given by equations $$$y = -x + q_i$$$ for some distinct $$$q_1, q_2, \ldots, q_m$$$.

DLS and JLS are interested in counting how many line pairs have integer intersection points, i.e. points with both coordinates that are integers. Unfortunately, the lesson will end up soon, so DLS and JLS are asking for your help.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases in the input. Then follow the test case descriptions.

The first line of a test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of lines drawn by DLS.

The second line of a test case contains $$$n$$$ distinct integers $$$p_i$$$ ($$$0 \le p_i \le 10^9$$$) describing the lines drawn by DLS. The integer $$$p_i$$$ describes a line given by the equation $$$y = x + p_i$$$.

The third line of a test case contains an integer $$$m$$$ ($$$1 \le m \le 10^5$$$), the number of lines drawn by JLS.

The fourth line of a test case contains $$$m$$$ distinct integers $$$q_i$$$ ($$$0 \le q_i \le 10^9$$$) describing the lines drawn by JLS. The integer $$$q_i$$$ describes a line given by the equation $$$y = -x + q_i$$$.

The sum of the values of $$$n$$$ over all test cases in the input does not exceed $$$10^5$$$. Similarly, the sum of the values of $$$m$$$ over all test cases in the input does not exceed $$$10^5$$$.

In hacks it is allowed to use only one test case in the input, so $$$t=1$$$ should be satisfied.

## Output Format
For each test case in the input print a single integer — the number of line pairs with integer intersection points.

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

## Note
The picture shows the lines from the first test case of the example. Black circles denote intersection points with integer coordinates.

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
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 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 two sets of integers: $$$A$$$ and $$$B$$$. You need to output the sum of elements in the set $$$C = \{x | x = a \oplus b, a \in A, b \in B\}$$$ modulo $$$998244353$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. Each number should be counted only once.

For example, if $$$A = \{2, 3\}$$$ and $$$B = \{2, 3\}$$$ you should count integer $$$1$$$ only once, despite the fact that you can get it as $$$3 \oplus 2$$$ and as $$$2 \oplus 3$$$. So the answer for this case is equal to $$$1 + 0 = 1$$$.

Let's call a segment $$$[l; r]$$$ a set of integers $$$\{l, l+1, \dots, r\}$$$.

The set $$$A$$$ is given as a union of $$$n_A$$$ segments, the set $$$B$$$ is given as a union of $$$n_B$$$ segments.

## Input Format
The first line contains a single integer $$$n_A$$$ ($$$1 \le n_A \le 100$$$).

The $$$i$$$-th of the next $$$n_A$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$), describing a segment of values of set $$$A$$$.

The next line contains a single integer $$$n_B$$$ ($$$1 \le n_B \le 100$$$).

The $$$i$$$-th of the next $$$n_B$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le 10^{18}$$$), describing a segment of values of set $$$B$$$.

Note that segments in both sets may intersect.

## Output Format
Print one integer — the sum of all elements in set $$$C = \{x | x = a \oplus b, a \in A, b \in B\}$$$ modulo $$$998244353$$$.

## Examples
```input
2
3 5
5 8
3
1 2
1 9
2 9
```
```output
112
```
-----
```input
1
1 9
2
2 4
2 10
```
```output
120
```

## Note
In the second example, we can discover that the set $$$C = \{0,1,\dots,15\}$$$, which means that all numbers between $$$0$$$ and $$$15$$$ can be represented as $$$a \oplus b$$$.

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
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 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
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 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
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 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
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 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
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 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
Adilbek was assigned to a special project. For Adilbek it means that he has $$$n$$$ days to run a special program and provide its results. But there is a problem: the program needs to run for $$$d$$$ days to calculate the results.

Fortunately, Adilbek can optimize the program. If he spends $$$x$$$ ($$$x$$$ is a non-negative integer) days optimizing the program, he will make the program run in $$$\left\lceil \frac{d}{x + 1} \right\rceil$$$ days ($$$\left\lceil a \right\rceil$$$ is the ceiling function: $$$\left\lceil 2.4 \right\rceil = 3$$$, $$$\left\lceil 2 \right\rceil = 2$$$). The program cannot be run and optimized simultaneously, so the total number of days he will spend is equal to $$$x + \left\lceil \frac{d}{x + 1} \right\rceil$$$.

Will Adilbek be able to provide the generated results in no more than $$$n$$$ days?

## Input Format
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 50$$$) — the number of test cases.

The next $$$T$$$ lines contain test cases – one per line. Each line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le d \le 10^9$$$) — the number of days before the deadline and the number of days the program runs.

## Output Format
Print $$$T$$$ answers — one per test case. For each test case print YES (case insensitive) if Adilbek can fit in $$$n$$$ days or NO (case insensitive) otherwise.

## Examples
```input
3
1 1
4 5
5 11
```
```output
YES
YES
NO
```

## Note
In the first test case, Adilbek decides not to optimize the program at all, since $$$d \le n$$$.

In the second test case, Adilbek can spend $$$1$$$ day optimizing the program and it will run $$$\left\lceil \frac{5}{2} \right\rceil = 3$$$ days. In total, he will spend $$$4$$$ days and will fit in the limit.

In the third test case, it's impossible to fit in the limit. For example, if Adilbek will optimize the program $$$2$$$ days, it'll still work $$$\left\lceil \frac{11}{2+1} \right\rceil = 4$$$ days.

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 two integers $$$A$$$ and $$$B$$$, calculate the number of pairs $$$(a, b)$$$ such that $$$1 \le a \le A$$$, $$$1 \le b \le B$$$, and the equation $$$a \cdot b + a + b = conc(a, b)$$$ is true; $$$conc(a, b)$$$ is the concatenation of $$$a$$$ and $$$b$$$ (for example, $$$conc(12, 23) = 1223$$$, $$$conc(100, 11) = 10011$$$). $$$a$$$ and $$$b$$$ should not contain leading zeroes.

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

Each test case contains two integers $$$A$$$ and $$$B$$$ $$$(1 \le A, B \le 10^9)$$$.

## Output Format
Print one integer — the number of pairs $$$(a, b)$$$ such that $$$1 \le a \le A$$$, $$$1 \le b \le B$$$, and the equation $$$a \cdot b + a + b = conc(a, b)$$$ is true.

## Examples
```input
3
1 11
4 2
191 31415926
```
```output
1
0
1337
```

## Note
There is only one suitable pair in the first test case: $$$a = 1$$$, $$$b = 9$$$ ($$$1 + 9 + 1 \cdot 9 = 19$$$).

Now solve the problem and return the code.