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

# Problem
Pak Chanek has a mirror in the shape of a circle. There are $$$N$$$ lamps on the circumference numbered from $$$1$$$ to $$$N$$$ in clockwise order. The length of the arc from lamp $$$i$$$ to lamp $$$i+1$$$ is $$$D_i$$$ for $$$1 \leq i \leq N-1$$$. Meanwhile, the length of the arc between lamp $$$N$$$ and lamp $$$1$$$ is $$$D_N$$$.

Pak Chanek wants to colour the lamps with $$$M$$$ different colours. Each lamp can be coloured with one of the $$$M$$$ colours. However, there cannot be three different lamps such that the colours of the three lamps are the same and the triangle made by considering the three lamps as vertices is a right triangle (triangle with one of its angles being exactly $$$90$$$ degrees).

The following are examples of lamp colouring configurations on the circular mirror.

Figure 1. an example of an incorrect colouring because lamps $$$1$$$, $$$2$$$, and $$$3$$$ form a right triangleFigure 2. an example of a correct colouringFigure 3. an example of a correct colouring

Before colouring the lamps, Pak Chanek wants to know the number of distinct colouring configurations he can make. Count the number of distinct possible lamp colouring configurations, modulo $$$998\,244\,353$$$.

## Input Format
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 3 \cdot 10^5$$$, $$$2 \le M \le 3 \cdot 10^5$$$) — the number of lamps in the mirror and the number of different colours used.

The second line contains $$$N$$$ integers $$$D_1, D_2, \ldots, D_N$$$ ($$$1 \le D_i \le 10^9$$$) — the lengths of the arcs between the lamps in the mirror.

## Output Format
An integer representing the number of possible lamp colouring configurations, modulo $$$998\,244\,353$$$.

## Examples
```input
4 2
10 10 6 14
```
```output
10
```
-----
```input
1 2
10
```
```output
2
```

## Note
In the first example, all correct lamp colouring configurations are $$$[1, 1, 2, 1]$$$, $$$[1, 1, 2, 2]$$$, $$$[1, 2, 1, 2]$$$, $$$[1, 2, 2, 1]$$$, $$$[1, 2, 2, 2]$$$, $$$[2, 1, 1, 1]$$$, $$$[2, 1, 1, 2]$$$, $$$[2, 1, 2, 1]$$$, $$$[2, 2, 1, 1]$$$, and $$$[2, 2, 1, 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: 128.0 MB

# Problem
Pak Chanek plans to build a garage. He wants the garage to consist of a square and a right triangle that are arranged like the following illustration.

Define $$$a$$$ and $$$b$$$ as the lengths of two of the sides in the right triangle as shown in the illustration. An integer $$$x$$$ is suitable if and only if we can construct a garage with assigning positive integer values for the lengths $$$a$$$ and $$$b$$$ ($$$a<b$$$) so that the area of the square at the bottom is exactly $$$x$$$. As a good friend of Pak Chanek, you are asked to help him find the $$$N$$$-th smallest suitable number.

## Input Format
The only line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^9$$$).

## Output Format
An integer that represents the $$$N$$$-th smallest suitable number.

## Examples
```input
3
```
```output
7
```

## Note
The $$$3$$$-rd smallest suitable number is $$$7$$$. A square area of $$$7$$$ can be obtained by assigning $$$a=3$$$ and $$$b=4$$$.

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
One day, Pak Chanek who is already bored of being alone at home decided to go traveling. While looking for an appropriate place, he found that Londonesia has an interesting structure.

According to the information gathered by Pak Chanek, there are $$$N$$$ cities numbered from $$$1$$$ to $$$N$$$. The cities are connected to each other with $$$N-1$$$ two-directional roads, with the $$$i$$$-th road connecting cities $$$U_i$$$ and $$$V_i$$$, and taking a time of $$$W_i$$$ hours to be traversed. In other words, Londonesia's structure forms a tree.

Pak Chanek wants to go on a journey in Londonesia starting and ending in any city (not necessarily the same city) such that each city is visited at least once with the least time possible. In order for the journey to end quicker, Pak Chanek also carries an instant teleportation device for moving from one city to any city that can only be used at most once. Help Pak Chanek for finding the minimum time needed.

Notes:

- Pak Chanek only needs to visit each city at least once. Pak Chanek does not have to traverse each road.
- In the journey, a city or a road can be visited more than once.

## Input Format
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of cities in Londonesia.

The $$$i$$$-th of the next $$$N-1$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ ($$$1 \le U_i, V_i \le N$$$, $$$1 \le W_i \le 10^9$$$) — a two-directional road that connects cities $$$U_i$$$ and $$$V_i$$$ that takes $$$W_i$$$ hours to be traversed. The roads in Londonesia form a tree.

## Output Format
Output one integer, which represents the minimum time in hours that is needed to visit each city at least once.

## Examples
```input
4
1 2 4
2 3 5
3 4 4
```
```output
8
```
-----
```input
5
1 2 45
1 3 50
1 4 10
1 5 65
```
```output
115
```

## Note
In the first example, the journey that has the minimum time is $$$2 → 1 \xrightarrow{\text{teleport}} 4 → 3$$$.

In the second example, the journey that has the minimum time is $$$3 → 1 → 4 → 1 → 2 \xrightarrow{\text{teleport}} 5$$$.

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
Pak Chanek is participating in a lemper cooking competition. In the competition, Pak Chanek has to cook lempers with $$$N$$$ stoves that are arranged sequentially from stove $$$1$$$ to stove $$$N$$$. Initially, stove $$$i$$$ has a temperature of $$$A_i$$$ degrees. A stove can have a negative temperature.

Pak Chanek realises that, in order for his lempers to be cooked, he needs to keep the temperature of each stove at a non-negative value. To make it happen, Pak Chanek can do zero or more operations. In one operation, Pak Chanek chooses one stove $$$i$$$ with $$$2 \leq i \leq N-1$$$, then:

1. changes the temperature of stove $$$i-1$$$ into $$$A_{i-1} := A_{i-1} + A_{i}$$$,
2. changes the temperature of stove $$$i+1$$$ into $$$A_{i+1} := A_{i+1} + A_{i}$$$, and
3. changes the temperature of stove $$$i$$$ into $$$A_i := -A_i$$$.

Pak Chanek wants to know the minimum number of operations he needs to do such that the temperatures of all stoves are at non-negative values. Help Pak Chanek by telling him the minimum number of operations needed or by reporting if it is not possible to do.

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

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$-10^9 \leq A_i \leq 10^9$$$) — the initial temperatures of the stoves.

## Output Format
Output an integer representing the minimum number of operations needed to make the temperatures of all stoves at non-negative values or output $$$-1$$$ if it is not possible.

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

## Note
For the first example, a sequence of operations that can be done is as follows:

- Pak Chanek does an operation to stove $$$3$$$, $$$A = [2, -2, 1, 4, 2, -2, 9]$$$.
- Pak Chanek does an operation to stove $$$2$$$, $$$A = [0, 2, -1, 4, 2, -2, 9]$$$.
- Pak Chanek does an operation to stove $$$3$$$, $$$A = [0, 1, 1, 3, 2, -2, 9]$$$.
- Pak Chanek does an operation to stove $$$6$$$, $$$A = [0, 1, 1, 3, 0, 2, 7]$$$.

There is no other sequence of operations such that the number of operations needed is fewer than $$$4$$$.

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

# Problem
Suppose $$$a_1, a_2, \dots, a_n$$$ is a sorted integer sequence of length $$$n$$$ such that $$$a_1 \leq a_2 \leq \dots \leq a_n$$$.

For every $$$1 \leq i \leq n$$$, the prefix sum $$$s_i$$$ of the first $$$i$$$ terms $$$a_1, a_2, \dots, a_i$$$ is defined by $$$$$$ s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i. $$$$$$

Now you are given the last $$$k$$$ terms of the prefix sums, which are $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$. Your task is to determine whether this is possible.

Formally, given $$$k$$$ integers $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$, the task is to check whether there is a sequence $$$a_1, a_2, \dots, a_n$$$ such that

1. $$$a_1 \leq a_2 \leq \dots \leq a_n$$$, and
2. $$$s_i = a_1 + a_2 + \dots + a_i$$$ for all $$$n-k+1 \leq i \leq n$$$.

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

The first line of each test case contains two integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and $$$k$$$ ($$$1 \leq k \leq n$$$), indicating the length of the sequence $$$a$$$ and the number of terms of prefix sums, respectively.

The second line of each test case contains $$$k$$$ integers $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$ for every $$$n-k+1 \leq i \leq n$$$).

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

## Output Format
For each test case, output "YES" (without quotes) if it is possible and "NO" (without quotes) otherwise.

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

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

## Note
In the first test case, we have the only sequence $$$a = [1, 1, 1, 1, 1]$$$.

In the second test case, we can choose, for example, $$$a = [-3, -2, -1, 0, 1, 2, 3]$$$.

In the third test case, the prefix sums define the only sequence $$$a = [2, 1, 1]$$$, but it is not sorted.

In the fourth test case, it can be shown that there is no sequence with the given prefix sums.

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: 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 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 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 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$$$ 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 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
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 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
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.