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

# Problem
Alice and Bob are playing a game on a sequence $$$a_1, a_2, \dots, a_n$$$ of length $$$n$$$. They move in turns and Alice moves first.

In the turn of each player, he or she should select an integer and remove it from the sequence. The game ends when there is no integer left in the sequence.

Alice wins if the sum of her selected integers is even; otherwise, Bob wins.

Your task is to determine who will win the game, if both players play optimally.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$), indicating the length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$), indicating the elements of the sequence.

## Output Format
For each test case, output "Alice" (without quotes) if Alice wins and "Bob" (without quotes) otherwise.

## Examples
```input
4
3
1 3 5
4
1 3 5 7
4
1 2 3 4
4
10 20 30 40
```
```output
Alice
Alice
Bob
Alice
```

## Note
In the first and second test cases, Alice always selects two odd numbers, so the sum of her selected numbers is always even. Therefore, Alice always wins.

In the third test case, Bob has a winning strategy that he always selects a number with the same parity as Alice selects in her last turn. Therefore, Bob always wins.

In the fourth test case, Alice always selects two even numbers, so the sum of her selected numbers is always even. Therefore, Alice always wins.

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
You are given three integers $$$a$$$, $$$b$$$, and $$$c$$$. Determine if one of them is the sum of the other two.

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

The description of each test case consists of three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a, b, c \leq 20$$$).

## Output Format
For each test case, output "YES" if one of the numbers is the sum of the other two, and "NO" otherwise.

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

## Examples
```input
7
1 4 3
2 5 8
9 11 20
0 0 0
20 20 20
4 12 3
15 7 8
```
```output
YES
NO
YES
YES
NO
NO
YES
```

## Note
In the first test case, $$$1 + 3 = 4$$$.

In the second test case, none of the numbers is the sum of the other two.

In the third test case, $$$9 + 11 = 20$$$.

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
You are given an array $$$a$$$ of $$$n$$$ positive integers. Determine if, by rearranging the elements, you can make the array strictly increasing. In other words, determine if it is possible to rearrange the elements such that $$$a_1 < a_2 < \dots < a_n$$$ holds.

## 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 a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the array.

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

## Output Format
For each test case, output "YES" (without quotes) if the array satisfies the condition, and "NO" (without quotes) otherwise.

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

## Examples
```input
3
4
1 1 1 1
5
8 7 1 3 4
1
5
```
```output
NO
YES
YES
```

## Note
In the first test case any rearrangement will keep the array $$$[1,1,1,1]$$$, which is not strictly increasing.

In the second test case, you can make the array $$$[1,3,4,7,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
On an $$$8 \times 8$$$ grid, some horizontal rows have been painted red, and some vertical columns have been painted blue, in some order. The stripes are drawn sequentially, one after the other. When the stripe is drawn, it repaints all the cells through which it passes.

Determine which color was used last.

The red stripe was painted after the blue one, so the answer is R.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 4000$$$) — the number of test cases. The description of test cases follows. There is an empty line before each test case.

Each test case consists of $$$8$$$ lines, each containing $$$8$$$ characters. Each of these characters is either 'R', 'B', or '.', denoting a red square, a blue square, and an unpainted square, respectively.

It is guaranteed that the given field is obtained from a colorless one by drawing horizontal red rows and vertical blue columns.

At least one stripe is painted.

## Output Format
For each test case, output 'R' if a red stripe was painted last, and 'B' if a blue stripe was painted last (without quotes).

## Examples
```input
4
....B...
....B...
....B...
RRRRRRRR
....B...
....B...
....B...
....B...
RRRRRRRB
B......B
B......B
B......B
B......B
B......B
B......B
RRRRRRRB
RRRRRRBB
.B.B..BB
RRRRRRBB
.B.B..BB
.B.B..BB
RRRRRRBB
.B.B..BB
.B.B..BB
........
........
........
RRRRRRRR
........
........
........
........
```
```output
R
B
B
R
```

## Note
The first test case is pictured in the statement.

In the second test case, the first blue column is painted first, then the first and last red rows, and finally the last blue column. Since a blue stripe is painted last, the answer is 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 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
Given an array of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$). Find the maximum value of $$$i + j$$$ such that $$$a_i$$$ and $$$a_j$$$ are coprime,$$$^{\dagger}$$$ or $$$-1$$$ if no such $$$i$$$, $$$j$$$ exist.

For example consider the array $$$[1, 3, 5, 2, 4, 7, 7]$$$. The maximum value of $$$i + j$$$ that can be obtained is $$$5 + 7$$$, since $$$a_5 = 4$$$ and $$$a_7 = 7$$$ are coprime.

$$$^{\dagger}$$$ Two integers $$$p$$$ and $$$q$$$ are coprime if the only positive integer that is a divisor of both of them is $$$1$$$ (that is, their greatest common divisor is $$$1$$$).

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

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

The following line contains $$$n$$$ space-separated positive integers $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — the elements of the array.

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

## Output Format
For each test case, output a single integer  — the maximum value of $$$i + j$$$ such that $$$i$$$ and $$$j$$$ satisfy the condition that $$$a_i$$$ and $$$a_j$$$ are coprime, or output $$$-1$$$ in case no $$$i$$$, $$$j$$$ satisfy the condition.

## Examples
```input
6
3
3 2 1
7
1 3 5 2 4 7 7
5
1 2 3 4 5
3
2 2 4
6
5 4 3 15 12 16
5
1 2 2 3 6
```
```output
6
12
9
-1
10
7
```

## Note
For the first test case, we can choose $$$i = j = 3$$$, with sum of indices equal to $$$6$$$, since $$$1$$$ and $$$1$$$ are coprime.

For the second test case, we can choose $$$i = 7$$$ and $$$j = 5$$$, with sum of indices equal to $$$7 + 5 = 12$$$, since $$$7$$$ and $$$4$$$ are coprime.

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
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 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
You have an array $$$a$$$ of size $$$n$$$ consisting only of zeroes and ones and an integer $$$k$$$. In one operation you can do one of the following:

- Select $$$2$$$ consecutive elements of $$$a$$$ and replace them with their minimum (that is, let $$$a := [a_{1}, a_{2}, \ldots, a_{i-1}, \min(a_{i}, a_{i+1}), a_{i+2}, \ldots, a_{n}]$$$ for some $$$1 \le i \le n-1$$$). This operation decreases the size of $$$a$$$ by $$$1$$$.
- Select $$$k$$$ consecutive elements of $$$a$$$ and replace them with their maximum (that is, let $$$a := [a_{1}, a_{2}, \ldots, a_{i-1}, \max(a_{i}, a_{i+1}, \ldots, a_{i+k-1}), a_{i+k}, \ldots, a_{n}]$$$ for some $$$1 \le i \le n-k+1$$$). This operation decreases the size of $$$a$$$ by $$$k-1$$$.

Determine if it's possible to turn $$$a$$$ into $$$[1]$$$ after several (possibly zero) operations.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 50$$$), the size of array $$$a$$$ and the length of segments that you can perform second type operation on.

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), elements of array $$$a$$$.

## Output Format
For each test case, if it is possible to turn $$$a$$$ into $$$[1]$$$, print "YES", otherwise print "NO".

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

## Note
In the first test case, you can perform the second type operation on second and third elements so $$$a$$$ becomes $$$[0, 1]$$$, then you can perform the second type operation on first and second elements, so $$$a$$$ turns to $$$[1]$$$.

In the fourth test case, it's obvious to see that you can't make any $$$1$$$, no matter what you do.

In the fifth test case, you can first perform a type 2 operation on the first three elements so that $$$a$$$ becomes $$$[1, 0, 0, 1]$$$, then perform a type 2 operation on the elements in positions two through four, so that $$$a$$$ becomes $$$[1, 1]$$$, and finally perform the first type operation on the remaining elements, so that $$$a$$$ becomes $$$[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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have an array $$$a$$$ of size $$$n$$$ consisting only of zeroes and ones. You can do the following operation:

- choose two indices $$$1 \le i , j \le n$$$, $$$i \ne j$$$,
- add $$$a_{i}$$$ to $$$a_{j}$$$,
- remove $$$a_{i}$$$ from $$$a$$$.

Note that elements of $$$a$$$ can become bigger than $$$1$$$ after performing some operations. Also note that $$$n$$$ becomes $$$1$$$ less after the operation.

What is the minimum number of operations needed to make $$$a$$$ non-decreasing, i. e. that each element is not less than the previous element?

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the size of array $$$a$$$.

Next line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), elements of array $$$a$$$.

It's guaranteed that sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case print a single integer, minimum number of operations needed to make $$$a$$$ non-decreasing.

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

## Note
In the first test case, $$$a$$$ is already non-decreasing, so you don't need to do any operations and the answer is $$$0$$$.

In the second test case, you can perform an operation for $$$i = 1$$$ and $$$j = 5$$$, so $$$a$$$ will be equal to $$$[0, 0, 1, 2]$$$ and it becomes non-decreasing.

In the third test case, you can perform an operation for $$$i = 2$$$ and $$$j = 1$$$, so $$$a$$$ will be equal to $$$[1]$$$ and it becomes non-decreasing.

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
You are given a rooted tree consisting of $$$n$$$ vertices. The vertices are numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$. You are also given a score array $$$s_1, s_2, \ldots, s_n$$$.

A multiset of $$$k$$$ simple paths is called valid if the following two conditions are both true.

- Each path starts from $$$1$$$.
- Let $$$c_i$$$ be the number of paths covering vertex $$$i$$$. For each pair of vertices $$$(u,v)$$$ ($$$2\le u,v\le n$$$) that have the same parent, $$$|c_u-c_v|\le 1$$$ holds.

It can be shown that it is always possible to find at least one valid multiset. Find the maximum value among all valid multisets.

## Input Format
Each test contains 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 first line of each test case contains two space-separated integers $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$1 \le k \le 10^9$$$) — the size of the tree and the required number of paths.

The second line contains $$$n - 1$$$ space-separated integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1\le p_i\le n$$$), where $$$p_i$$$ is the parent of the $$$i$$$-th vertex. It is guaranteed that this value describe a valid tree with root $$$1$$$.

The third line contains $$$n$$$ space-separated integers $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \le s_i \le 10^4$$$) — the scores of the vertices.

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, print a single integer — the maximum value of a path multiset.

## Examples
```input
2
5 4
1 2 1 3
6 2 1 5 7
5 3
1 2 1 3
6 6 1 4 10
```
```output
54
56
```

## Note
In the first test case, one of optimal solutions is four paths $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, $$$1 \to 4$$$, here $$$c=[4,2,2,2,2]$$$. The value equals to $$$4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54$$$.

In the second test case, one of optimal solution is three paths $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, here $$$c=[3,2,2,1,2]$$$. The value equals to $$$3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56$$$.

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
Anton decided to get ready for an Olympiad in Informatics. Ilya prepared $$$n$$$ tasks for him to solve. It is possible to submit the solution for the $$$i$$$-th task in the first $$$d_{i}$$$ days only. Anton cannot solve more than one task a day. Ilya estimated the usefulness of the $$$i$$$-th tasks as $$$r_{i}$$$ and divided the tasks into three topics, the topic of the $$$i$$$-th task is $$$type_{i}$$$.

Anton wants to solve exactly $$$a$$$ tasks on the first topic, $$$b$$$ tasks on the second topic and $$$c$$$ tasks on the third topic. Tell Anton if it is possible to do so, and if it is, calculate the maximum total usefulness of the tasks he may solve.

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

The first line of each test case contains four integers $$$n, a, b, c$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le a, b, c \le n$$$).

The following $$$n$$$ lines contain three integers each — $$$r_i, type_i, d_i$$$ ($$$0 \le r_i \le 10^{9}$$$, $$$1 \le type_i \le 3$$$, $$$1 \le d_i \le n$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print $$$-1$$$ if Anton cannot reach his goal; otherwise, print the maximum usefulness of the tasks he will solve.

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

## Note
In the first test case from the sample test Anton can solve tasks $$$2$$$ and $$$4$$$.

In the second test case from the sample test it is impossible to fulfill Anton's wish.

In the third test case from the sample test it is optimal to solve tasks $$$2$$$, $$$3$$$ and $$$4$$$.

In the last test case from the sample test it is optimal to solve tasks $$$1$$$, $$$2$$$ and $$$4$$$.

Now solve the problem and return the code.