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

# Problem
You are developing a rating system for an online game. Every time a player participates in a match, the player's rating changes depending on the results.

Initially, the player's rating is $$$0$$$. There are $$$n$$$ matches; after the $$$i$$$-th match, the rating change is equal to $$$a_i$$$ (the rating increases by $$$a_i$$$ if $$$a_i$$$ is positive, or decreases by $$$|a_i|$$$ if it's negative. There are no zeros in the sequence $$$a$$$).

The system has an additional rule: for a fixed integer $$$k$$$, if a player's rating has reached the value $$$k$$$, it will never fall below it. Formally, if a player's rating at least $$$k$$$, and a rating change would make it less than $$$k$$$, then the rating will decrease to exactly $$$k$$$.

Your task is to determine the value $$$k$$$ in such a way that the player's rating after all $$$n$$$ matches is the maximum possible (among all integer values of $$$k$$$). If there are multiple possible answers, you can print any of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of matches.

The second line contains $$$n$$$ integer $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$; $$$a_i \ne 0$$$) — the rating change after the $$$i$$$-th match.

The sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print one integer $$$m$$$ ($$$-10^{18} \le m \le 10^{18}$$$) — the value of $$$k$$$ such that the rating of the player will be the maximum possible when using this value. It can be shown that at least one of the optimal answers meets the constraint $$$-10^{18} \le m \le 10^{18}$$$.

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

## Note
In the first example, if $$$k=3$$$, then the rating changes as follows: $$$0 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 6$$$.

In the second example, if $$$k=0$$$, then the rating changes as follows: $$$0 \rightarrow 0 \rightarrow 0 \rightarrow 0$$$.

In the third example, if $$$k=25$$$, then the rating changes as follows: $$$0 \rightarrow 4 \rightarrow 6$$$.

In the fourth example, if $$$k=6$$$, then the rating changes as follows: $$$0 \rightarrow 5 \rightarrow 6 \rightarrow 6 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ boxes placed in a line. The boxes are numbered from $$$1$$$ to $$$n$$$. Some boxes contain one ball inside of them, the rest are empty. At least one box contains a ball and at least one box is empty.

In one move, you have to choose a box with a ball inside and an adjacent empty box and move the ball from one box into another. Boxes $$$i$$$ and $$$i+1$$$ for all $$$i$$$ from $$$1$$$ to $$$n-1$$$ are considered adjacent to each other. Boxes $$$1$$$ and $$$n$$$ are not adjacent.

How many different arrangements of balls exist after exactly $$$k$$$ moves are performed? Two arrangements are considered different if there is at least one such box that it contains a ball in one of them and doesn't contain a ball in the other one.

Since the answer might be pretty large, print its remainder modulo $$$10^9+7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1500$$$; $$$1 \le k \le 1500$$$) — the number of boxes and the number of moves.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{0, 1\}$$$) — $$$0$$$ denotes an empty box and $$$1$$$ denotes a box with a ball inside. There is at least one $$$0$$$ and at least one $$$1$$$.

## Output Format
Print a single integer — the number of different arrangements of balls that can exist after exactly $$$k$$$ moves are performed, modulo $$$10^9+7$$$.

## Examples
```input
4 1
1 0 1 0
```
```output
3
```
-----
```input
4 2
1 0 1 0
```
```output
2
```
-----
```input
10 6
1 0 0 1 0 0 0 1 1 1
```
```output
69
```

## Note
In the first example, there are the following possible arrangements:

- 0 1 1 0 — obtained after moving the ball from box $$$1$$$ to box $$$2$$$;
- 1 0 0 1 — obtained after moving the ball from box $$$3$$$ to box $$$4$$$;
- 1 1 0 0 — obtained after moving the ball from box $$$3$$$ to box $$$2$$$.

In the second example, there are the following possible arrangements:

- 1 0 1 0 — three ways to obtain that: just reverse the operation performed during the first move;
- 0 1 0 1 — obtained from either of the first two arrangements after the first move.

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
Monocarp always starts his morning with a good ol' sandwich. Sandwiches Monocarp makes always consist of bread, cheese and/or ham.

A sandwich always follows the formula:

- a piece of bread
- a slice of cheese or ham
- a piece of bread
- $$$\dots$$$
- a slice of cheese or ham
- a piece of bread

So it always has bread on top and at the bottom, and it alternates between bread and filling, where filling is a slice of either cheese or ham. Each piece of bread and each slice of cheese or ham is called a layer.

Today Monocarp woke up and discovered that he has $$$b$$$ pieces of bread, $$$c$$$ slices of cheese and $$$h$$$ slices of ham. What is the maximum number of layers his morning sandwich can have?

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

Each testcase consists of three integers $$$b, c$$$ and $$$h$$$ ($$$2 \le b \le 100$$$; $$$1 \le c, h \le 100$$$) — the number of pieces of bread, slices of cheese and slices of ham, respectively.

## Output Format
For each testcase, print a single integer — the maximum number of layers Monocarp's morning sandwich can have.

## Examples
```input
3
2 1 1
10 1 2
3 7 8
```
```output
3
7
5
```

## Note
In the first testcase, Monocarp can arrange a sandwich with three layers: either a piece of bread, a slice of cheese and another piece of bread, or a piece of bread, a slice of ham and another piece of bread.

In the second testcase, Monocarp has a lot of bread, but not too much filling. He can arrange a sandwich with four pieces of bread, one slice of cheese and two slices of ham.

In the third testcase, it's the opposite — Monocarp has a lot of filling, but not too much bread. He can arrange a sandwich with three pieces of bread and two slices of cheese, for example.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Monocarp is playing yet another computer game. And yet again, his character is killing some monsters. There are $$$n$$$ monsters, numbered from $$$1$$$ to $$$n$$$, and the $$$i$$$-th of them has $$$a_i$$$ health points initially.

Monocarp's character has an ability that deals $$$k$$$ damage to the monster with the highest current health. If there are several of them, the one with the smaller index is chosen. If a monster's health becomes less than or equal to $$$0$$$ after Monocarp uses his ability, then it dies.

Monocarp uses his ability until all monsters die. Your task is to determine the order in which monsters will die.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — the number of monsters and the damage which Monocarp's ability deals.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial health points of monsters.

The sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print $$$n$$$ integers — the indices of monsters in the order they die.

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

## Note
In the first example, the health points change as follows: $$$[1, 2, \underline{3}] \rightarrow [1, \underline{2}, 1] \rightarrow [\underline{1}, 0, 1] \rightarrow [-1, 0, \underline{1}] \rightarrow [-1, 0, -1]$$$. The monster that is going to take damage the next time Monocarp uses his ability is underlined.

In the second example, the health points change as follows: $$$[\underline{1}, 1] \rightarrow [-2, \underline{1}] \rightarrow [-2, -2]$$$.

In the third example, the health points change as follows: $$$[2, \underline{8}, 3, 5] \rightarrow [2, \underline{5}, 3, 5] \rightarrow [2, 2, 3, \underline{5}] \rightarrow [2, 2, \underline{3}, 2] \rightarrow [\underline{2}, 2, 0, 2] \rightarrow [-1, \underline{2}, 0, 2] \rightarrow [-1, -1, 0, \underline{2}] \rightarrow [-1, -1, 0, -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 given a string $$$s$$$ consisting of $$$n$$$ characters 0 and/or 1.

You make $$$m$$$ copies of this string, let the $$$i$$$-th copy be the string $$$t_i$$$. Then you perform exactly one operation on each of the copies: for the $$$i$$$-th copy, you sort its substring $$$[l_i; r_i]$$$ (the substring from the $$$l_i$$$-th character to the $$$r_i$$$-th character, both endpoints inclusive). Note that each operation affects only one copy, and each copy is affected by only one operation.

Your task is to calculate the number of different strings among $$$t_1, t_2, \ldots, t_m$$$. Note that the initial string $$$s$$$ should be counted only if at least one of the copies stays the same after the operation.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of $$$s$$$ and the number of copies, respectively.

The second line contains $$$n$$$ characters 0 and/or 1 — the string $$$s$$$.

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the description of the operation applied to the $$$i$$$-th copy.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$. The sum of $$$m$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print one integer — the number of different strings among $$$t_1, t_2, \ldots, t_m$$$.

## Examples
```input
3
6 5
101100
1 2
1 3
2 4
5 5
1 6
6 4
100111
2 2
1 4
1 3
1 2
1 1
0
1 1
```
```output
3
3
1
```

## Note
Consider the first example. Copies below are given in order of the input operations. Underlined substrings are substrings that are sorted:

1. 101100 $$$\rightarrow$$$ 011100;
2. 101100 $$$\rightarrow$$$ 011100;
3. 101100 $$$\rightarrow$$$ 101100;
4. 101100 $$$\rightarrow$$$ 101100;
5. 101100 $$$\rightarrow$$$ 000111.

There are three different strings among $$$t_1, t_2, t_3, t_4, t_5$$$: 000111, 011100 and 101100.

Consider the second example:

1. 100111 $$$\rightarrow$$$ 100111;
2. 100111 $$$\rightarrow$$$ 001111;
3. 100111 $$$\rightarrow$$$ 001111;
4. 100111 $$$\rightarrow$$$ 010111.

There are three different strings among $$$t_1, t_2, t_3, t_4$$$: 001111, 010111 and 100111.

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 given an array of $$$n$$$ integers, where each integer is either $$$0$$$, $$$1$$$, or $$$2$$$. Initially, each element of the array is blue.

Your goal is to paint each element of the array red. In order to do so, you can perform operations of two types:

- pay one coin to choose a blue element and paint it red;
- choose a red element which is not equal to $$$0$$$ and a blue element adjacent to it, decrease the chosen red element by $$$1$$$, and paint the chosen blue element red.

What is the minimum number of coins you have to spend to achieve your goal?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2$$$).

## Output Format
Print one integer — the minimum number of coins you have to spend in order to paint all elements red.

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

## Note
In the first example, you can paint all elements red with having to spend only one coin as follows:

1. paint the $$$2$$$-nd element red by spending one coin;
2. decrease the $$$2$$$-nd element by $$$1$$$ and paint the $$$1$$$-st element red;
3. decrease the $$$2$$$-nd element by $$$1$$$ and paint the $$$3$$$-rd element red.

In the second example, you can paint all elements red spending only two coins as follows:

1. paint the $$$4$$$-th element red by spending one coin;
2. decrease the $$$4$$$-th element by $$$1$$$ and paint the $$$3$$$-rd element red;
3. paint the $$$1$$$-st element red by spending one coin;
4. decrease the $$$3$$$-rd element by $$$1$$$ and paint the $$$2$$$-nd element red.

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: 7.0 seconds
Memory limit: 512.0 MB

# Problem
For a set of integers $$$S$$$, let's define its cost as the minimum value of $$$x \oplus y$$$ among all pairs of different integers from the set (here, $$$\oplus$$$ denotes bitwise XOR). If there are less than two elements in the set, its cost is equal to $$$2^{30}$$$.

You are given a set of integers $$$\{a_1, a_2, \dots, a_n\}$$$. You have to partition it into two sets $$$S_1$$$ and $$$S_2$$$ in such a way that every element of the given set belongs to exactly one of these two sets. The value of the partition is the minimum among the costs of $$$S_1$$$ and $$$S_2$$$.

Find the partition with the maximum possible value.

## Input Format
The first line contains $$$n$$$ ($$$2 \le n \le 200000$$$) — the number of elements in the set.

The second line contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — the elements of the set.

## Output Format
Print a string $$$n$$$ characters 0 and/or 1 describing the partition as follows: the $$$i$$$-th character should be 0 if the element $$$a_i$$$ belongs to $$$S_1$$$, otherwise, that character should be 1.

If there are multiple optimal answers, print any of them.

## Examples
```input
5
42 13 1337 37 152
```
```output
10001
```
-----
```input
4
1 2 3 4
```
```output
1100
```
-----
```input
2
1 2
```
```output
10
```
-----
```input
8
7 6 5 4 3 2 1 0
```
```output
10010110
```

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 have an array of integers $$$a$$$ of length $$$n$$$. You can apply the following operation to the given array:

- Swap two elements $$$a_i$$$ and $$$a_j$$$ such that $$$i \neq j$$$, $$$a_i$$$ and $$$a_j$$$ are either both even or both odd.

Determine whether it is possible to sort the array in non-decreasing order by performing the operation any number of times (possibly zero).

For example, let $$$a$$$ = [$$$7, 10, 1, 3, 2$$$]. Then we can perform $$$3$$$ operations to sort the array:

1. Swap $$$a_3 = 1$$$ and $$$a_1 = 7$$$, since $$$1$$$ and $$$7$$$ are odd. We get $$$a$$$ = [$$$1, 10, 7, 3, 2$$$];
2. Swap $$$a_2 = 10$$$ and $$$a_5 = 2$$$, since $$$10$$$ and $$$2$$$ are even. We get $$$a$$$ = [$$$1, 2, 7, 3, 10$$$];
3. Swap $$$a_4 = 3$$$ and $$$a_3 = 7$$$, since $$$3$$$ and $$$7$$$ are odd. We get $$$a$$$ = [$$$1, 2, 3, 7, 10$$$].

## Input Format
The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The description of the test cases follows.

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

The second line of each test case contains exactly $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of 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 on a separate line:

- YES if the array can be sorted by applying the operation to it some number of times;
- NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).

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

## Note
The first test case is explained in the problem statement.

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
Your friends have an array of $$$n$$$ elements, calculated its array of prefix sums and passed it to you, accidentally losing one element during the transfer. Your task is to find out if the given array can matches permutation.

A permutation of $$$n$$$ elements is an array of $$$n$$$ numbers from $$$1$$$ to $$$n$$$ such that each number occurs exactly one times in it.

The array of prefix sums of the array $$$a$$$ — is such an array $$$b$$$ that $$$b_i = \sum_{j=1}^i a_j, 1 \le i \le n$$$.

For example, the original permutation was $$$[1, 5, 2, 4, 3]$$$. Its array of prefix sums — $$$[1, 6, 8, 12, 15]$$$. Having lost one element, you can get, for example, arrays $$$[6, 8, 12, 15]$$$ or $$$[1, 6, 8, 15]$$$.

It can also be shown that the array $$$[1, 2, 100]$$$ does not correspond to any permutation.

## Input Format
The first line contains a positive number $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of the description of each test case contains a positive number $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the size of the initial array.

The second line of the description of each test case contains $$$n - 1$$$ positive number $$$a_i$$$ ($$$1 \le a_i \le 10^{18}$$$), $$$a_{i-1} < a_i$$$ — elements of the array of prefix sums.

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 "YES" if such a permutation exists, and "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive response).

## Examples
```input
12
5
6 8 12 15
5
1 6 8 15
4
1 2 100
4
1 3 6
2
2
3
1 2
4
3 7 10
5
5 44 46 50
4
1 9 10
5
13 21 36 42
5
1 2 3 1000000000000000000
9
9 11 12 20 25 28 30 33
```
```output
YES
YES
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
```

## Note
In the fourth example, for example, the permutation $$$[1, 2, 3, 4]$$$ is suitable. In the fifth example, for example, the permutation $$$[2, 1]$$$ is suitable. In the seventh example, for example, the permutation $$$[1, 2, 4, 3]$$$ is suitable.

Now solve the problem and return the code.