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
Petya and his friend, robot Petya++, like to solve exciting math problems.

One day Petya++ came up with the numbers $$$n$$$ and $$$x$$$ and wrote the following equality on the board: $$$$$$n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,$$$$$$ where $$$\&$$$ denotes the bitwise AND operation. Then he suggested his friend Petya find such a minimal $$$m$$$ ($$$m \ge n$$$) that the equality on the board holds.

Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer.

Can you solve this difficult problem?

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

The only line of each test case contains two integers $$$n$$$, $$$x$$$ ($$$0\le n, x \le 10^{18}$$$).

## Output Format
For every test case, output the smallest possible value of $$$m$$$ such that equality holds.

If the equality does not hold for any $$$m$$$, print $$$-1$$$ instead.

We can show that if the required $$$m$$$ exists, it does not exceed $$$5 \cdot 10^{18}$$$.

## Examples
```input
5
10 8
10 10
10 42
20 16
1000000000000000000 0
```
```output
12
10
-1
24
1152921504606846976
```

## Note
In the first example, $$$10\ \&\ 11 = 10$$$, but $$$10\ \&\ 11\ \&\ 12 = 8$$$, so the answer is $$$12$$$.

In the second example, $$$10 = 10$$$, so the answer is $$$10$$$.

In the third example, we can see that the required $$$m$$$ does not exist, so we have to print $$$-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
Today Hayato came home from school with homework.

In the assignment, Hayato was given an array $$$a$$$ of length $$$n$$$. The task was to find $$$3$$$ numbers in this array whose sum is odd. At school, he claimed that there are such $$$3$$$ numbers, but Hayato was not sure, so he asked you for help.

Answer if there are such three numbers, and if so, output indices $$$i$$$, $$$j$$$, and $$$k$$$ such that $$$a_i + a_j + a_k$$$ is odd.

The odd numbers are integers that are not divisible by $$$2$$$: $$$1$$$, $$$3$$$, $$$5$$$, and so on.

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

For each test case, the first line contains one integer $$$n$$$ ($$$3 \le n \le 300$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the array $$$a$$$.

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

## Output Format
For each test case, in the first line print one word "YES" (without quotes) if there are $$$3$$$ numbers with an odd sum or "NO" (without quotes) if there are no such $$$3$$$ numbers.

If the answer exists, then on the second line print $$$3$$$ distinct integers $$$i, j, k$$$ ($$$1 \le i, j, k \le n$$$) — the indices of the numbers. If there are several answers, output any.

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

## Note
In the first test case, there is one way to choose $$$3$$$ numbers, and since $$$1 + 1 + 1 = 3$$$, this triple is fine for us.

In the second test case, you need to choose the numbers $$$1, 2, 2$$$, since $$$1 + 2 + 2 = 5$$$.

In the third test case, there is one way to choose three numbers, but $$$1 + 2 + 3 = 6$$$ is an even number, so the required triple does not exist.

In the fifth test case, no matter what three numbers we choose, their sum is even.

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
While at Kira's house, Josuke saw a piece of paper on the table with a task written on it.

The task sounded as follows. There is an array $$$a$$$ of length $$$n$$$. On this array, do the following:

- select an integer $$$k > 1$$$;
- split the array into $$$k$$$ subsegments $$$^\dagger$$$;
- calculate the sum in each of $$$k$$$ subsegments and write these sums to another array $$$b$$$ (where the sum of the subsegment $$$(l, r)$$$ is $$${\sum_{j = l}^{r}a_j}$$$);
- the final score of such a split will be $$$\gcd(b_1, b_2, \ldots, b_k)^\ddagger$$$.

The task is to find such a partition that the score is maximum possible. Josuke is interested in this task but is not strong in computer science. Help him to find the maximum possible score.

$$$^\dagger$$$ A division of an array into $$$k$$$ subsegments is $$$k$$$ pairs of numbers $$$(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$ such that $$$l_i \le r_i$$$ and for every $$$1 \le j \le k - 1$$$ $$$l_{j + 1} = r_j + 1$$$, also $$$l_1 = 1$$$ and $$$r_k = n$$$. These pairs represent the subsegments.

$$$^\ddagger$$$ $$$\gcd(b_1, b_2, \ldots, b_k)$$$ stands for the greatest common divisor (GCD) of the array $$$b$$$.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9 $$$) — the array $$$a$$$ itself.

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 score for the optimal partition.

## Examples
```input
6
4
2 2 1 3
2
1 2
3
1 4 5
6
1 2 1 1 1 3
10
12 30 37 88 12 78 89 17 2 12
6
7 7 7 7 7 7
```
```output
4
1
5
3
1
21
```

## Note
In the first test case, you can choose $$$k = 2$$$ and split the array into subsegments $$$(1, 2)$$$ and $$$(3, 4)$$$.

Then the score of such a partition will be equal to $$$\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4$$$.

In the fourth test case, you can choose $$$k = 3$$$ and split the array into subsegments $$$(1, 2), (3, 5), (6, 6)$$$.

The split score is $$$\gcd(1 + 2, 1 + 1 + 1, 3) = 3$$$.

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
Josuke received a huge undirected weighted complete$$$^\dagger$$$ graph $$$G$$$ as a gift from his grandfather. The graph contains $$$10^{18}$$$ vertices. The peculiarity of the gift is that the weight of the edge between the different vertices $$$u$$$ and $$$v$$$ is equal to $$$\gcd(u, v)^\ddagger$$$. Josuke decided to experiment and make a new graph $$$G'$$$. To do this, he chooses two integers $$$l \le r$$$ and deletes all vertices except such vertices $$$v$$$ that $$$l \le v \le r$$$, and also deletes all the edges except between the remaining vertices.

Now Josuke is wondering how many different weights are there in $$$G'$$$. Since their count turned out to be huge, he asks for your help.

$$$^\dagger$$$ A complete graph is a simple undirected graph in which every pair of distinct vertices is adjacent.

$$$^\ddagger$$$ $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of the numbers $$$x$$$ and $$$y$$$.

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

The first line of each test case contains two numbers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$, $$$l \le 10^9$$$).

## Output Format
For each test case print a single number — the number of different weights among the remaining edges.

## Examples
```input
7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090
```
```output
2
6
3
5
0
5
50045
```

## Note
The graph $$$G'$$$ for the first test case.

The picture above shows that the graph has $$$2$$$ different weights.

In the fifth test case, there is only one vertex from which no edges originate, so the answer is $$$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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Today is an important day for chef Tonio — an auditor has arrived in his hometown of Morioh. He has also arrived at Tonio's restaurant and ordered dessert. Tonio has not been prepared for this turn of events.

As you know, dessert is a string of lowercase English letters. Tonio remembered the rule of desserts — a string $$$s$$$ of length $$$n$$$. Any dessert $$$t$$$ is delicious if the number of occurrences of $$$t$$$ in $$$s$$$ as a substring is divisible by the length of $$$t$$$.

Now Tonio wants to know the number of delicious substrings of $$$s$$$. If the substring occurs several times in the string $$$s$$$, then all occurrences must be taken into account.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of the rule $$$s$$$.

The second line contains the string $$$s$$$ of length $$$n$$$ — the rule. The rule consists only of lowercase English letters.

## Output Format
In a single line print the number of delicious substrings of $$$s$$$.

## Examples
```input
7
abacaba
```
```output
11
```
-----
```input
8
abaababa
```
```output
11
```
-----
```input
10
deadinside
```
```output
12
```
-----
```input
5
aaaaa
```
```output
12
```

## Note
In the first sample, there are many delicious substrings. $$$7$$$ of them are substrings of length $$$1$$$ (because any number is divisible by $$$1$$$). Consider other delicious substrings:

- "ab" occurs in $$$s$$$ $$$2$$$ times, which is divisible by the length of the substring.
- "ba" also occurs $$$2$$$ times.

Therefore, the answer is $$$7 + 2 + 2 = 11$$$.

Note that the answer includes both occurrences of "ab" and "ba".

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$$$ such that exactly one of these two equations is true:

- $$$a+b=c$$$
- $$$a-b=c$$$

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

The description of each test case consists of three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \leq a, b \leq 9$$$, $$$-8 \leq c \leq 18$$$). The additional constraint on the input: it will be generated so that exactly one of the two equations will be true.

## Output Format
For each test case, output either + or - on a new line, representing the correct equation.

## Examples
```input
11
1 2 3
3 2 1
2 9 -7
3 4 7
1 1 2
1 1 0
3 3 6
9 9 18
9 9 0
1 9 -8
1 9 10
```
```output
+
-
-
+
+
-
+
+
-
-
+
```

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

In the second test case, $$$3-2=1$$$.

In the third test case, $$$2-9=-7$$$. Note that $$$c$$$ can be negative.

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 palindrome is a string that reads the same from left to right as from right to left. For example, abacaba, aaaa, abba, racecar are palindromes.

You are given a string $$$s$$$ consisting of lowercase Latin letters. The string $$$s$$$ is a palindrome.

You have to check whether it is possible to rearrange the letters in it to get another palindrome (not equal to the given string $$$s$$$).

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

The only line of each test case contains a string $$$s$$$ ($$$2 \le |s| \le 50$$$) consisting of lowercase Latin letters. This string is a palindrome.

## Output Format
For each test case, print YES if it is possible to rearrange the letters in the given string to get another palindrome. Otherwise, print NO.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
3
codedoc
gg
aabaa
```
```output
YES
NO
NO
```

## Note
In the first test case, it is possible to rearrange the letters in the palindrome codedoc to obtain the string ocdedco, which is different from the given string, but also a palindrome.

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
The only difference between easy and hard versions is the maximum values of $$$n$$$ and $$$q$$$.

You are given an array, consisting of $$$n$$$ integers. Initially, all elements are red.

You can apply the following operation to the array multiple times. During the $$$i$$$-th operation, you select an element of the array; then:

- if the element is red, it increases by $$$i$$$ and becomes blue;
- if the element is blue, it decreases by $$$i$$$ and becomes red.

The operations are numbered from $$$1$$$, i. e. during the first operation some element is changed by $$$1$$$ and so on.

You are asked $$$q$$$ queries of the following form:

- given an integer $$$k$$$, what can the largest minimum in the array be if you apply exactly $$$k$$$ operations to it?

Note that the operations don't affect the array between queries, all queries are asked on the initial array $$$a$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 1000$$$) — the number of elements in the array and the number of queries.

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

The third line contains $$$q$$$ integers $$$k_1, k_2, \dots, k_q$$$ ($$$1 \le k_j \le 10^9$$$).

## Output Format
For each query, print a single integer — the largest minimum that the array can have after you apply exactly $$$k$$$ operations to it.

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

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
The only difference between easy and hard versions is the maximum values of $$$n$$$ and $$$q$$$.

You are given an array, consisting of $$$n$$$ integers. Initially, all elements are red.

You can apply the following operation to the array multiple times. During the $$$i$$$-th operation, you select an element of the array; then:

- if the element is red, it increases by $$$i$$$ and becomes blue;
- if the element is blue, it decreases by $$$i$$$ and becomes red.

The operations are numbered from $$$1$$$, i. e. during the first operation some element is changed by $$$1$$$ and so on.

You are asked $$$q$$$ queries of the following form:

- given an integer $$$k$$$, what can the largest minimum in the array be if you apply exactly $$$k$$$ operations to it?

Note that the operations don't affect the array between queries, all queries are asked on the initial array $$$a$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of elements in the array and the number of queries.

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

The third line contains $$$q$$$ integers $$$k_1, k_2, \dots, k_q$$$ ($$$1 \le k_j \le 10^9$$$).

## Output Format
For each query, print a single integer — the largest minimum that the array can have after you apply exactly $$$k$$$ operations to it.

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

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: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
Recall that the binomial coefficient $$$\binom{x}{y}$$$ is calculated as follows ($$$x$$$ and $$$y$$$ are non-negative integers):

- if $$$x < y$$$, then $$$\binom{x}{y} = 0$$$;
- otherwise, $$$\binom{x}{y} = \frac{x!}{y! \cdot (x-y)!}$$$.

You are given an array $$$a_1, a_2, \dots, a_n$$$ and an integer $$$k$$$. You have to calculate a new array $$$b_1, b_2, \dots, b_n$$$, where

- $$$b_1 = (\binom{1}{k} \cdot a_1) \bmod 998244353$$$;
- $$$b_2 = (\binom{2}{k} \cdot a_1 + \binom{1}{k} \cdot a_2) \bmod 998244353$$$;
- $$$b_3 = (\binom{3}{k} \cdot a_1 + \binom{2}{k} \cdot a_2 + \binom{1}{k} \cdot a_3) \bmod 998244353$$$, and so on.

Formally, $$$b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353$$$.

Note that the array is given in a modified way, and you have to output it in a modified way as well.

## Input Format
The only line of the input contains six integers $$$n$$$, $$$a_1$$$, $$$x$$$, $$$y$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 10^7$$$; $$$0 \le a_1, x, y < m$$$; $$$2 \le m \le 998244353$$$; $$$1 \le k \le 5$$$).

The array $$$[a_1, a_2, \dots, a_n]$$$ is generated as follows:

- $$$a_1$$$ is given in the input;
- for $$$2 \le i \le n$$$, $$$a_i = (a_{i-1} \cdot x + y) \bmod m$$$.

## Output Format
Since outputting up to $$$10^7$$$ integers might be too slow, you have to do the following:

Let $$$c_i = b_i \cdot i$$$ (without taking modulo $$$998244353$$$ after the multiplication). Print the integer $$$c_1 \oplus c_2 \oplus \dots \oplus c_n$$$, where $$$\oplus$$$ denotes the bitwise XOR operator.

## Examples
```input
5 8 2 3 100 2
```
```output
1283
```

Now solve the problem and return the code.