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

# Problem
Rudolph invented the game of tic-tac-toe for three players. It has classic rules, except for the third player who plays with pluses. Rudolf has a $$$3 \times 3$$$ field  — the result of the completed game. Each field cell contains either a cross, or a nought, or a plus sign, or nothing. The game is won by the player who makes a horizontal, vertical or diagonal row of $$$3$$$'s of their symbols.

Rudolph wants to find the result of the game. Either exactly one of the three players won or it ended in a draw. It is guaranteed that multiple players cannot win at the same time.

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

Each test case consists of three lines, each of which consists of three characters. The symbol can be one of four: "X" means a cross, "O" means a nought, "+" means a plus, "." means an empty cell.

## Output Format
For each test case, print the string "X" if the crosses won, "O" if the noughts won, "+" if the pluses won, "DRAW" if there was a draw.

## Examples
```input
5
+X+
OXO
OX.
O+.
+OX
X+O
.XO
OX.
+++
O.+
X.O
+..
.++
X.O
+..
```
```output
X
O
+
DRAW
DRAW
```

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
Rudolph drew a beautiful Christmas tree and decided to print the picture. However, the ink in the cartridge often runs out at the most inconvenient moment. Therefore, Rudolph wants to calculate in advance how much green ink he will need.

The tree is a vertical trunk with identical triangular branches at different heights. The thickness of the trunk is negligible.

Each branch is an isosceles triangle with base $$$d$$$ and height $$$h$$$, whose base is perpendicular to the trunk. The triangles are arranged upward at an angle, and the trunk passes exactly in the middle. The base of the $$$i$$$-th triangle is located at a height of $$$y_i$$$.

The figure below shows an example of a tree with $$$d = 4, h = 2$$$ and three branches with bases at heights $$$[1, 4, 5]$$$.

Help Rudolph calculate the total area of the tree branches.

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

Then follow the descriptions of the test cases.

The first line of each test case contains three integers $$$n, d, h$$$ ($$$1 \le n, d, h \le 2 \cdot 10^5$$$) — the number of branches, the length of the base, and the height of the branches, respectively.

The second line of each test case contains $$$n$$$ integers $$$y_i$$$ $$$(1 \le y_i \le 10^9, y_1 < y_2 < ... < y_n)$$$ — the heights of the bases of the branches.

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

## Output Format
For each test case, output a single real number on a separate line — the total area of the tree branches. The answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

## Examples
```input
5
3 4 2
1 4 5
1 5 1
3
4 6 6
1 2 3 4
2 1 200000
1 200000
2 4 3
9 11
```
```output
11
2.5
34.5
199999.9999975
11.333333
```

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
A new bonus system has been introduced at Vika's favorite cosmetics store, "Golden Pear"!

The system works as follows: suppose a customer has $$$b$$$ bonuses. Before paying for the purchase, the customer can choose one of two options:

- Get a discount equal to the current number of bonuses, while the bonuses are not deducted.
- Accumulate an additional $$$x$$$ bonuses, where $$$x$$$ is the last digit of the number $$$b$$$. As a result, the customer's account will have $$$b+x$$$ bonuses.

For example, if a customer had $$$24$$$ bonuses, he can either get a discount of $$$24$$$ or accumulate an additional $$$4$$$ bonuses, after which his account will have $$$28$$$ bonuses.

At the moment, Vika has already accumulated $$$s$$$ bonuses.

The girl knows that during the remaining time of the bonus system, she will make $$$k$$$ more purchases at the "Golden Pear" store network.

After familiarizing herself with the rules of the bonus system, Vika became interested in the maximum total discount she can get.

Help the girl answer this question.

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

The test case consists of a single line containing two integers $$$s$$$ and $$$k$$$ ($$$0 \le s \le 10^9$$$, $$$1 \le k \le 10^9$$$) — the current number of bonuses in Vika's account and how many more purchases the girl will make.

## Output Format
For each test case, output a single integer — the maximum total discount that can be obtained through the bonus system.

## Examples
```input
6
1 3
11 3
0 179
5 1000000000
723252212 856168102
728598293 145725253
```
```output
4
33
0
9999999990
1252047198518668448
106175170582793129
```

## Note
In the first test case, Vika can accumulate bonuses after the first and second purchases, after which she can get a discount of $$$4$$$.

In the second test case, Vika can get a discount of $$$11$$$ three times, and the total discount will be $$$33$$$.

In the third example, regardless of Vika's actions, she will always get a total discount of $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Recently, Vika was studying her favorite internet resource - Wikipedia.

On the expanses of Wikipedia, she read about an interesting mathematical operation bitwise XOR, denoted by $$$\oplus$$$.

Vika began to study the properties of this mysterious operation. To do this, she took an array $$$a$$$ consisting of $$$n$$$ non-negative integers and applied the following operation to all its elements at the same time: $$$a_i = a_i \oplus a_{(i+1) \bmod n}$$$. Here $$$x \bmod y$$$ denotes the remainder of dividing $$$x$$$ by $$$y$$$. The elements of the array are numbered starting from $$$0$$$.

Since it is not enough to perform the above actions once for a complete study, Vika repeats them until the array $$$a$$$ becomes all zeros.

Determine how many of the above actions it will take to make all elements of the array $$$a$$$ zero. If this moment never comes, output $$$-1$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2^{20}$$$) - the length of the array $$$a$$$.

It is guaranteed that $$$n$$$ can be represented as $$$2^k$$$ for some integer $$$k$$$ ($$$0 \le k \le 20$$$).

The second line contains $$$n$$$ integers $$$a_0, a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 10^9$$$) - the elements of the array $$$a$$$.

## Output Format
Output a single number - the minimum number of actions required to make all elements of the array $$$a$$$ zero, or $$$-1$$$ if the array $$$a$$$ will never become zero.

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

## Note
In the first example, after one operation, the array $$$a$$$ will become equal to $$$[3, 3, 3, 3]$$$. After one more operation, it will become equal to $$$[0, 0, 0, 0]$$$.

In the second example, the array $$$a$$$ initially consists only of zeros.

In the third example, after one operation, the array $$$a$$$ will become equal to $$$[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
Suneet has three digits $$$a$$$, $$$b$$$, and $$$c$$$.

Since math isn't his strongest point, he asks you to determine if you can choose any two digits to make a sum greater or equal to $$$10$$$.

Output "YES" if there is such a pair, and "NO" otherwise.

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

The only line of each test case contains three digits $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a, b, c \leq 9$$$).

## Output Format
For each test case, output "YES" if such a pair exists, 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
5
8 1 2
4 4 5
9 9 9
0 0 0
8 5 3
```
```output
YES
NO
YES
NO
YES
```

## Note
For the first test case, by choosing the digits $$$8$$$ and $$$2$$$ we can obtain a sum of $$$8 + 2 = 10$$$ which satisfies the condition, thus the output should be "YES".

For the second test case, any combination of chosen digits won't be at least $$$10$$$, thus the output should be "NO" (note that we can not choose the digit on the same position twice).

For the third test case, any combination of chosen digits will have a sum equal to $$$18$$$, thus the output should be "YES".

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
In the game show "Ten Words of Wisdom", there are $$$n$$$ participants numbered from $$$1$$$ to $$$n$$$, each of whom submits one response. The $$$i$$$-th response is $$$a_i$$$ words long and has quality $$$b_i$$$. No two responses have the same quality, and at least one response has length at most $$$10$$$.

The winner of the show is the response which has the highest quality out of all responses that are not longer than $$$10$$$ words. Which response is the winner?

## 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 50$$$) — the number of responses.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 50$$$) — the number of words and the quality of the $$$i$$$-th response, respectively.

Additional constraints on the input: in each test case, at least one value of $$$i$$$ satisfies $$$a_i \leq 10$$$, and all values of $$$b_i$$$ are distinct.

## Output Format
For each test case, output a single line containing one integer $$$x$$$ ($$$1 \leq x \leq n$$$) — the winner of the show, according to the rules given in the statement.

It can be shown that, according to the constraints in the statement, exactly one winner exists for each test case.

## Examples
```input
3
5
7 2
12 5
9 3
9 4
10 1
3
1 2
3 4
5 6
1
1 43
```
```output
4
3
1
```

## Note
In the first test case, the responses provided are as follows:

- Response 1: $$$7$$$ words, quality $$$2$$$
- Response 2: $$$12$$$ words, quality $$$5$$$
- Response 3: $$$9$$$ words, quality $$$3$$$
- Response 4: $$$9$$$ words, quality $$$4$$$
- Response 5: $$$10$$$ words, quality $$$1$$$

We can see that the responses with indices $$$1$$$, $$$3$$$, $$$4$$$, and $$$5$$$ have lengths not exceeding $$$10$$$ words. Out of these responses, the winner is the one with the highest quality.

Comparing the qualities, we find that:

- Response 1 has quality $$$2$$$.
- Response 3 has quality $$$3$$$.
- Response 4 has quality $$$4$$$.
- Response 5 has quality $$$1$$$.

Among these responses, Response 4 has the highest quality.

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
A compass points directly toward the morning star. It can only point in one of eight directions: the four cardinal directions (N, S, E, W) or some combination (NW, NE, SW, SE). Otherwise, it will break.

The directions the compass can point.

There are $$$n$$$ distinct points with integer coordinates on a plane. How many ways can you put a compass at one point and the morning star at another so that the compass does not break?

## 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 a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of points.

Then $$$n$$$ lines follow, each line containing two integers $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — the coordinates of each point, all points have distinct coordinates.

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

## Output Format
For each test case, output a single integer — the number of pairs of points that don't break the compass.

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

## Note
In the first test case, any pair of points won't break the compass:

- The compass is at $$$(0,0)$$$, the morning star is at $$$(-1,-1)$$$: the compass will point $$$\text{SW}$$$.
- The compass is at $$$(0,0)$$$, the morning star is at $$$(1,1)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(-1,-1)$$$, the morning star is at $$$(0,0)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(-1,-1)$$$, the morning star is at $$$(1,1)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(1,1)$$$, the morning star is at $$$(0,0)$$$: the compass will point $$$\text{SW}$$$.
- The compass is at $$$(1,1)$$$, the morning star is at $$$(-1,-1)$$$: the compass will point $$$\text{SW}$$$.

In the second test case, only two pairs of points won't break the compass:

- The compass is at $$$(6,9)$$$, the morning star is at $$$(10,13)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(10,13)$$$, the morning star is at $$$(6,9)$$$: the compass will point $$$\text{SW}$$$.

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
There are $$$n$$$ teams in a football tournament. Each pair of teams match up once. After every match, Pak Chanek receives two integers as the result of the match, the number of goals the two teams score during the match. The efficiency of a team is equal to the total number of goals the team scores in each of its matches minus the total number of goals scored by the opponent in each of its matches.

After the tournament ends, Pak Dengklek counts the efficiency of every team. Turns out that he forgot about the efficiency of one of the teams. Given the efficiency of $$$n-1$$$ teams $$$a_1,a_2,a_3,\ldots,a_{n-1}$$$. What is the efficiency of the missing team? It can be shown that the efficiency of the missing team can be uniquely determined.

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

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of teams.

The second line contains $$$n-1$$$ integers $$$a_1,a_2,a_3,\ldots,a_{n-1}$$$ ($$$-100\leq a_i\leq100$$$) — the efficiency of $$$n-1$$$ teams.

## Output Format
For each test case, output a line containing an integer representing the efficiency of the missing team.

## Examples
```input
2
4
3 -4 5
11
-30 12 -57 7 0 -81 -68 41 -89 0
```
```output
-4
265
```

## Note
In the first test case, below is a possible tournament result:

- Team $$$1$$$ vs. Team $$$2$$$: $$$1-2$$$
- Team $$$1$$$ vs. Team $$$3$$$: $$$3-0$$$
- Team $$$1$$$ vs. Team $$$4$$$: $$$3-2$$$
- Team $$$2$$$ vs. Team $$$3$$$: $$$1-4$$$
- Team $$$2$$$ vs. Team $$$4$$$: $$$1-3$$$
- Team $$$3$$$ vs. Team $$$4$$$: $$$5-0$$$

The efficiency of each team is:

1. Team $$$1$$$: $$$(1+3+3)-(2+0+2)=7-4=3$$$
2. Team $$$2$$$: $$$(2+1+1)-(1+4+3)=4-8=-4$$$
3. Team $$$3$$$: $$$(0+4+5)-(3+1+0)=9-4=5$$$
4. Team $$$4$$$: $$$(2+3+0)-(3+1+5)=5-9=-4$$$

Therefore, the efficiency of the missing team (team $$$4$$$) is $$$-4$$$.

It can be shown that any possible tournament of $$$4$$$ teams that has the efficiency of $$$3$$$ teams be $$$3$$$, $$$-4$$$, and $$$5$$$ will always have the efficiency of the $$$4$$$-th team be $$$-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 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
Chaneka, a gamer kid, invented a new gaming controller called joyboard. Interestingly, the joyboard she invented can only be used to play one game.

The joyboard has a screen containing $$$n+1$$$ slots numbered from $$$1$$$ to $$$n+1$$$ from left to right. The $$$n+1$$$ slots are going to be filled with an array of non-negative integers $$$[a_1,a_2,a_3,\ldots,a_{n+1}]$$$. Chaneka, as the player, must assign $$$a_{n+1}$$$ with an integer between $$$0$$$ and $$$m$$$ inclusive. Then, for each $$$i$$$ from $$$n$$$ to $$$1$$$, the value of $$$a_i$$$ will be equal to the remainder of dividing $$$a_{i+1}$$$ (the adjacent value to the right) by $$$i$$$. In other words, $$$a_i = a_{i + 1} \bmod i$$$.

Chaneka wants it such that after every slot is assigned with an integer, there are exactly $$$k$$$ distinct values in the entire screen (among all $$$n+1$$$ slots). How many valid ways are there for assigning a non-negative integer into slot $$$n+1$$$?

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

The only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 10^9$$$; $$$0 \leq m \leq 10^9$$$; $$$1 \leq k \leq n+1$$$) — there are $$$n+1$$$ slots, the integer assigned in slot $$$n+1$$$ must not be bigger than $$$m$$$, and there should be exactly $$$k$$$ distinct values.

## Output Format
For each test case, output a line containing an integer representing the number of valid ways for assigning a non-negative integer into slot $$$n+1$$$.

## Examples
```input
4
4 6 3
2 0 1
265 265 265
3 10 2
```
```output
2
1
0
5
```

## Note
In the first test case, one of the $$$2$$$ possible ways for Chaneka is to choose $$$a_{n+1}=6$$$. If she does that, then:

- $$$a_4=a_5\bmod 4=6\bmod 4=2$$$
- $$$a_3=a_4\bmod 3=2\bmod 3=2$$$
- $$$a_2=a_3\bmod 2=2\bmod 2=0$$$
- $$$a_1=a_2\bmod 1=0\bmod 1=0$$$
- $$$a = [0, 0, 2, 2, 6]$$$
- There are $$$3$$$ distinct values.

In the second test case, the $$$1$$$ possible way for Chaneka is to choose $$$a_{n+1}=0$$$. If she does that, then $$$a = [0, 0, 0]$$$. There is only $$$1$$$ distinct value.

In the third test case, there is no possible way for assigning a non-negative integer into slot $$$n+1$$$.

Now solve the problem and return the code.