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
Timur has a stairway with $$$n$$$ steps. The $$$i$$$-th step is $$$a_i$$$ meters higher than its predecessor. The first step is $$$a_1$$$ meters higher than the ground, and the ground starts at $$$0$$$ meters.

The stairs for the first test case.

Timur has $$$q$$$ questions, each denoted by an integer $$$k_1, \dots, k_q$$$. For each question $$$k_i$$$, you have to print the maximum possible height Timur can achieve by climbing the steps if his legs are of length $$$k_i$$$. Timur can only climb the $$$j$$$-th step if his legs are of length at least $$$a_j$$$. In other words, $$$k_i \geq a_j$$$ for each step $$$j$$$ climbed.

Note that you should answer each question independently.

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

The first line of each test case contains two integers $$$n, q$$$ ($$$1 \leq n, q \leq 2\cdot10^5$$$) — the number of steps and the number of questions, respectively.

The second line of each test case contains $$$n$$$ integers ($$$1 \leq a_i \leq 10^9$$$) — the height of the steps.

The third line of each test case contains $$$q$$$ integers ($$$0 \leq k_i \leq 10^9$$$) — the numbers for each question.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot10^5$$$, and the sum of $$$q$$$ does not exceed $$$2\cdot10^5$$$.

## Output Format
For each test case, output a single line containing $$$q$$$ integers, the answer for each question.

Please note, that the answer for some questions won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

## Examples
```input
3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000
```
```output
1 4 4 9 9 
0 2 
3000000000
```

## Note
Consider the first test case, pictured in the statement.

- If Timur's legs have length $$$1$$$, then he can only climb stair $$$1$$$, so the highest he can reach is $$$1$$$ meter.
- If Timur's legs have length $$$2$$$ or $$$4$$$, then he can only climb stairs $$$1$$$, $$$2$$$, and $$$3$$$, so the highest he can reach is $$$1+2+1=4$$$ meters.
- If Timur's legs have length $$$9$$$ or $$$10$$$, then he can climb the whole staircase, so the highest he can reach is $$$1+2+1+5=9$$$ meters.

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 an array $$$a$$$ consisting of $$$n$$$ integers. You want to distribute these $$$n$$$ integers into two groups $$$s_1$$$ and $$$s_2$$$ (groups can be empty) so that the following conditions are satisfied:

- For each $$$i$$$ $$$(1 \leq i \leq n)$$$, $$$a_i$$$ goes into exactly one group.
- The value $$$|sum(s_1)| - |sum(s_2)|$$$ is the maximum possible among all such ways to distribute the integers.Here $$$sum(s_1)$$$ denotes the sum of the numbers in the group $$$s_1$$$, and $$$sum(s_2)$$$ denotes the sum of the numbers in the group $$$s_2$$$.

Determine the maximum possible value of $$$|sum(s_1)| - |sum(s_2)|$$$.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^4)$$$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$  — the length of the array $$$a$$$.

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

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

## Output Format
For each test case, output a single integer  — the maximum possible value of $$$|sum(s_1)| - |sum(s_2)|$$$.

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

## Note
In the first testcase, we can distribute as $$$s_1 = \{10\}$$$, $$$s_2 = \{-10\}$$$. Then the value will be $$$|10| - |-10| = 0$$$.

In the second testcase, we can distribute as $$$s_1 = \{0, 11, -1\}$$$, $$$s_2 = \{-2\}$$$. Then the value will be $$$|0 + 11 - 1| - |-2| = 10 - 2 = 8$$$.

In the third testcase, we can distribute as $$$s_1 = \{2, 3, 2\}$$$, $$$s_2 = \{\}$$$. Then the value will be $$$|2 + 3 + 2| - |0| = 7$$$.

In the fourth testcase, we can distribute as $$$s_1 = \{-9, -4, 0\}$$$, $$$s_2 = \{2, 0\}$$$. Then the value will be $$$|-9 - 4 + 0| - |2 + 0| = 13 - 2 = 11$$$.

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

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Alice and Bob are playing a game on an array $$$a$$$ of $$$n$$$ positive integers. Alice and Bob make alternating moves with Alice going first.

In his/her turn, the player makes the following move:

- If $$$a_1 = 0$$$, the player loses the game, otherwise:
- Player chooses some $$$i$$$ with $$$2\le i \le n$$$. Then player decreases the value of $$$a_1$$$ by $$$1$$$ and swaps $$$a_1$$$ with $$$a_i$$$.

Determine the winner of the game if both players play optimally.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^4)$$$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$  — the length of the array $$$a$$$.

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

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

## Output Format
For each test case, if Alice will win the game, output "Alice". Otherwise, output "Bob".

You can output each letter in any case. For example, "alIcE", "Alice", "alice" will all be considered identical.

## Examples
```input
3
2
1 1
2
2 1
3
5 4 4
```
```output
Bob
Alice
Alice
```

## Note
In the first testcase, in her turn, Alice can only choose $$$i = 2$$$, making the array equal $$$[1, 0]$$$. Then Bob, in his turn, will also choose $$$i = 2$$$ and make the array equal $$$[0, 0]$$$. As $$$a_1 = 0$$$, Alice loses.

In the second testcase, once again, players can only choose $$$i = 2$$$. Then the array will change as follows: $$$[2, 1] \to [1, 1] \to [1, 0] \to [0, 0]$$$, and Bob loses.

In the third testcase, we can show that Alice has a winning strategy.

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 an array $$$a$$$ of $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$.

You have to answer $$$q$$$ independent queries, each consisting of two integers $$$l$$$ and $$$r$$$.

- Consider the subarray $$$a[l:r]$$$ $$$=$$$ $$$[a_l, a_{l+1}, \ldots, a_r]$$$. You can apply the following operation to the subarray any number of times (possibly zero)-   Choose two integers $$$L$$$, $$$R$$$ such that $$$l \le L \le R \le r$$$ and $$$R - L + 1$$$ is odd.  Replace each element in the subarray from $$$L$$$ to $$$R$$$ with the XOR of the elements in the subarray $$$[L, R]$$$.
- The answer to the query is the minimum number of operations required to make all elements of the subarray $$$a[l:r]$$$ equal to $$$0$$$ or $$$-1$$$ if it is impossible to make all of them equal to $$$0$$$.

You can find more details about XOR operation here.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 2 \cdot 10^5)$$$  — the length of the array $$$a$$$ and the number of queries.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \lt 2^{30})$$$  — the elements of the array $$$a$$$.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$  — the description of the $$$i$$$-th query.

## Output Format
For each query, output a single integer  — the answer to that query.

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

## Note
In the first query, $$$l = 3, r = 4$$$, subarray = $$$[3, 3]$$$. We can apply operation only to the subarrays of length $$$1$$$, which won't change the array; hence it is impossible to make all elements equal to $$$0$$$.

In the second query, $$$l = 4, r = 6$$$, subarray = $$$[3, 1, 2]$$$. We can choose the whole subarray $$$(L = 4, R = 6)$$$ and replace all elements by their XOR $$$(3 \oplus 1 \oplus 2) = 0$$$, making the subarray $$$[0, 0, 0]$$$.

In the fifth query, $$$l = 1, r = 6$$$, subarray = $$$[3, 0, 3, 3, 1, 2]$$$. We can make the operations as follows:

1. Choose $$$L = 4, R = 6$$$, making the subarray $$$[3, 0, 3, 0, 0, 0]$$$.
2. Choose $$$L = 1, R = 5$$$, making the subarray $$$[0, 0, 0, 0, 0, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
For given integers $$$n$$$ and $$$m$$$, let's call a pair of arrays $$$a$$$ and $$$b$$$ of integers good, if they satisfy the following conditions:

- $$$a$$$ and $$$b$$$ have the same length, let their length be $$$k$$$.
- $$$k \ge 2$$$ and $$$a_1 = 0, a_k = n, b_1 = 0, b_k = m$$$.
- For each $$$1 < i \le k$$$ the following holds: $$$a_i \geq a_{i - 1}$$$, $$$b_i \geq b_{i - 1}$$$, and $$$a_i + b_i \neq a_{i - 1} + b_{i - 1}$$$.

Find the sum of $$$|a|$$$ over all good pairs of arrays $$$(a,b)$$$. Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t (1 \leq t \leq 10^4)$$$  — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 5 \cdot 10^6)$$$.

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

## Output Format
For each test case, output a single integer  — the sum of $$$|a|$$$ over all good pairs of arrays $$$(a,b)$$$ modulo $$$10^9 + 7$$$.

## Examples
```input
4
1 1
1 2
2 2
100 100
```
```output
8
26
101
886336572
```

## Note
In the first testcase, the good pairs of arrays are

- $$$([0, 1], [0, 1])$$$, length = $$$2$$$.
- $$$([0, 1, 1], [0, 0, 1])$$$, length = $$$3$$$.
- $$$([0, 0, 1], [0, 1, 1])$$$, length = $$$3$$$.

Hence the sum of the lengths would be $$${2 + 3 + 3} = 8$$$.

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

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Beppa and her circle of geek friends keep up to date on a group chat in the instant messaging app SwerChat$$$^{\text{TM}}$$$.

The group has $$$n$$$ members, excluding Beppa. Each of those members has a unique ID between $$$1$$$ and $$$n$$$. When a user opens a group chat, SwerChat$$$^{\text{TM}}$$$ displays the list of other members of that group, sorted by decreasing times of last seen online (so the member who opened the chat most recently is the first of the list). However, the times of last seen are not displayed.

Today, Beppa has been busy all day: she has only opened the group chat twice, once at 9:00 and once at 22:00. Both times, she wrote down the list of members in the order they appeared at that time. Now she wonders: what is the minimum number of other members that must have been online at least once between 9:00 and 22:00?

Beppa is sure that no two members are ever online at the same time and no members are online when Beppa opens the group chat at 9:00 and 22:00.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of members of the group excluding Beppa.

The second line contains $$$n$$$ integers $$$a_1, \, a_2, \, \dots, \, a_n$$$ ($$$1 \le a_i \le n$$$) — the list of IDs of the members, sorted by decreasing times of last seen online at 9:00.

The third line contains $$$n$$$ integers $$$b_1, \, b_2, \, \dots, \, b_n$$$ ($$$1 \le b_i \le n$$$) — the list of IDs of the members, sorted by decreasing times of last seen online at 22:00.

For all $$$1\le i < j\le n$$$, it is guaranteed that $$$a_i \ne a_j$$$ and $$$b_i \ne b_j$$$.

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

## Output Format
For each test case, print the minimum number of members that must have been online between 9:00 and 22:00.

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

## Note
In the first test case, members $$$4, 5$$$ must have been online between 9:00 and 22:00.

In the second test case, it is possible that nobody has been online between 9:00 and 22:00.

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 at your grandparents' house and you are playing an old video game on a strange console. Your controller has only two buttons and each button has a number written on it.

Initially, your score is $$$0$$$. The game is composed of $$$n$$$ rounds. For each $$$1\le i\le n$$$, the $$$i$$$-th round works as follows.

On the screen, a symbol $$$s_i$$$ appears, which is either $$$\texttt{+}$$$ (plus) or $$$\texttt{-}$$$ (minus). Then you must press one of the two buttons on the controller once. Suppose you press a button with the number $$$x$$$ written on it: your score will increase by $$$x$$$ if the symbol was $$$\texttt{+}$$$ and will decrease by $$$x$$$ if the symbol was $$$\texttt{-}$$$. After you press the button, the round ends.

After you have played all $$$n$$$ rounds, you win if your score is $$$0$$$.

Over the years, your grandparents bought many different controllers, so you have $$$q$$$ of them. The two buttons on the $$$j$$$-th controller have the numbers $$$a_j$$$ and $$$b_j$$$ written on them. For each controller, you must compute whether you can win the game playing with that controller.

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

The second line contains a string $$$s$$$ of length $$$n$$$ — where $$$s_i$$$ is the symbol that will appear on the screen in the $$$i$$$-th round. It is guaranteed that $$$s$$$ contains only the characters $$$\texttt{+}$$$ and $$$\texttt{-}$$$.

The third line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of controllers.

The following $$$q$$$ lines contain two integers $$$a_j$$$ and $$$b_j$$$ each ($$$1 \le a_j, b_j \le 10^9$$$) — the numbers on the buttons of controller $$$j$$$.

## Output Format
Output $$$q$$$ lines. On line $$$j$$$ print $$$\texttt{YES}$$$ if the game is winnable using controller $$$j$$$, otherwise print $$$\texttt{NO}$$$.

## Examples
```input
8
+-+---+-
5
2 1
10 3
7 9
10 10
5 3
```
```output
YES
NO
NO
NO
YES
```
-----
```input
6
+-++--
2
9 7
1 1
```
```output
YES
YES
```
-----
```input
20
+-----+--+--------+-
2
1000000000 99999997
250000000 1000000000
```
```output
NO
YES
```

## Note
In the first sample, one possible way to get score $$$0$$$ using the first controller is by pressing the button with numnber $$$1$$$ in rounds $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$ and $$$8$$$, and pressing the button with number $$$2$$$ in rounds $$$3$$$ and $$$7$$$. It is possible to show that there is no way to get a score of $$$0$$$ using the second controller.

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
The "Parmigiana di melanzane" is a typical Italian dish. Alessandro and Bianca have very different tastes when it comes to it: Alessandro loves to eat Parmigiana with seafood, but Bianca thinks it is an atrocity! To decide which ingredients to include in the dish they prepare, they play the following game.

There are $$$n$$$ possible ingredients, labeled from $$$1$$$ to $$$n$$$. The higher the label, the closer the ingredient is to being seafood. The ingredients are connected by $$$n - 1$$$ edges, in such a way as to form a tree. Alessandro and Bianca take turns, with Alessandro going first. They alternately choose a terminal ingredient $$$x$$$, that is an ingredient currently connected to at most one other ingredient, and remove it from the tree. If the terminal ingredient $$$x$$$ was chosen by Alessandro, it goes in the recipe; if it was chosen by Bianca, it is discarded.

The taste of the Parmigiana is measured as the maximum label of an ingredient in the recipe. Alessandro wants to maximize the taste, while Bianca wants to minimize the taste. If both play optimally, what is the taste of the Parmigiana?

## Input Format
The first line contains an integer $$$n$$$ ($$$2\le n \le 100\,000$$$) — the number of ingredients.

Each of the following $$$n-1$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — the ingredients that the $$$i$$$-th edge connects.

It is guaranteed that the edges form a tree (i.e., any pair of ingredients is connected by the edges, possibly indirectly).

## Output Format
Print the value of the taste if both Alessandro and Bianca play optimally.

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

## Note
In the first sample, Alessandro can choose terminal ingredient $$$4$$$ in the first turn. This ingredient is added to the recipe. Since $$$4$$$ is the maximum label of an ingredient, the taste is $$$4$$$ regardless of the choices that follow.

In the second sample, Bianca can make sure that neither ingredient $$$4$$$ nor $$$5$$$ are included in the recipe, in which case Alessandro can include $$$3$$$. Thus, the taste is $$$3$$$.

Now solve the problem and return the code.