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
John is a lead programmer on a destroyer belonging to the space navy of the Confederacy of Independent Operating Systems. One of his tasks is checking if the electronic brains of robots were damaged during battles.

A standard test is to order the robots to form one or several lines, in each line the robots should stand one after another. After that, each robot reports the number of robots standing in front of it in its line.

An example of robots' arrangement (the front of the lines is on the left). The robots report the numbers above.

The $$$i$$$-th robot reported number $$$l_i$$$. Unfortunately, John does not know which line each robot stands in, and can't check the reported numbers. Please determine if it is possible to form the lines in such a way that all reported numbers are correct, or not.

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

The first line in each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of robots.

The second line in each test case contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$0 \leq l_i < 100$$$), $$$l_i$$$ is equal to the number of robots in front of the $$$i$$$-th robot in its line.

The sum of $$$n$$$ over all test cases won't exceed $$$200$$$.

## Output Format
For each test case, output "YES", if there exists a robot arrangement consistent with robots' reports. Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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

## Note
Example arrangement consistent with robot statements from the first example test case:

Example arrangement consistent with robot statements from the second example is shown in the statement.

In the third test case, the third robot claims that there are two machines in front of it. In such a case, the robot directly in front of it would have one machine in front. No robot claims that, so there is no valid arrangement.

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

# Problem
A prime number is a positive integer that has exactly two different positive divisors: $$$1$$$ and the integer itself. For example, $$$2$$$, $$$3$$$, $$$13$$$ and $$$101$$$ are prime numbers; $$$1$$$, $$$4$$$, $$$6$$$ and $$$42$$$ are not.

You are given a sequence of digits from $$$1$$$ to $$$9$$$, in which every digit from $$$1$$$ to $$$9$$$ appears exactly once.

You are allowed to do the following operation several (maybe zero) times: choose any digit from the sequence and delete it. However, you cannot perform this operation if the sequence consists of only two digits.

Your goal is to obtain a sequence which represents a prime number. Note that you cannot reorder the digits in the sequence.

Print the resulting sequence, or report that it is impossible to perform the operations so that the resulting sequence is a prime number.

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

Each test case consists of one line containing a string of $$$9$$$ digits (without any characters between them). Each digit from $$$1$$$ to $$$9$$$ appears in this string exactly once.

## Output Format
For each test case, print the answer on a separate line as follows:

- if it is impossible to perform the described operations, print $$$-1$$$;
- otherwise, print any sequence that represents a prime number, which can be obtained from the given string performing several (maybe zero) operations described in the statement. If there are multiple such sequences, you can print any one of them.

## Examples
```input
4
123456789
987654321
243567918
576318429
```
```output
167
53
3571
57638429
```

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 $$$a$$$ of length $$$n$$$, consisting of positive integers.

You can perform the following operation on this array any number of times (possibly zero):

- choose three integers $$$l$$$, $$$r$$$ and $$$x$$$ such that $$$1 \le l \le r \le n$$$, and multiply every $$$a_i$$$ such that $$$l \le i \le r$$$ by $$$x$$$.

Note that you can choose any integer as $$$x$$$, it doesn't have to be positive.

You have to calculate the minimum number of operations to make the array $$$a$$$ sorted in strictly ascending order (i. e. the condition $$$a_1 < a_2 < \dots < a_n$$$ must be satisfied).

## 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 one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)  — the length of the array $$$a$$$.

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

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the minimum number of operations required to make $$$a$$$ sorted in strictly ascending order.

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

## Note
In the first test case, we can perform the operations as follows:

- $$$l = 2$$$, $$$r = 4$$$, $$$x = 3$$$;
- $$$l = 4$$$, $$$r = 4$$$, $$$x = 2$$$;
- $$$l = 5$$$, $$$r = 5$$$, $$$x = 10$$$.

In the second test case, we can perform one operation as follows:

- $$$l = 1$$$, $$$r = 4$$$, $$$x = -2$$$;
- $$$l = 6$$$, $$$r = 6$$$, $$$x = 1337$$$.

In the third test case, the array $$$a$$$ is already sorted.

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 $$$a$$$ of length $$$n$$$ consisting of non-negative integers.

You have to calculate the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, where $$$f(l, r)$$$ is $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} \oplus a_r$$$ (the character $$$\oplus$$$ denotes bitwise XOR).

Since the answer can be very large, print it modulo $$$998244353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

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

## Output Format
Print the one integer — the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, taken modulo $$$998244353$$$.

## Examples
```input
3
1 3 2
```
```output
12
```
-----
```input
4
39 68 31 80
```
```output
1337
```
-----
```input
7
313539461 779847196 221612534 488613315 633203958 394620685 761188160
```
```output
257421502
```

## Note
In the first example, the answer is equal to $$$f(1, 1) + 2 \cdot f(1, 2) + 3 \cdot f(1, 3) + f(2, 2) + 2 \cdot f(2, 3) + f(3, 3) = $$$ $$$= 1 + 2 \cdot 2 + 3 \cdot 0 + 3 + 2 \cdot 1 + 2 = 12$$$.

Now solve the problem and return the code.