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

# Problem
Baby Ehab was toying around with arrays. He has an array $$$a$$$ of length $$$n$$$. He defines an array to be good if there's no way to partition it into $$$2$$$ subsequences such that the sum of the elements in the first is equal to the sum of the elements in the second. Now he wants to remove the minimum number of elements in $$$a$$$ so that it becomes a good array. Can you help him?

A sequence $$$b$$$ is a subsequence of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly zero or all) elements. A partitioning of an array is a way to divide it into $$$2$$$ subsequences such that every element belongs to exactly one subsequence, so you must use all the elements, and you can't share any elements.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 2000$$$) — the elements of the array $$$a$$$.

## Output Format
The first line should contain the minimum number of elements you need to remove.

The second line should contain the indices of the elements you're removing, separated by spaces.

We can show that an answer always exists. If there are multiple solutions, you can print any.

## Examples
```input
4
6 3 9 12
```
```output
1
2
```
-----
```input
2
1 2
```
```output
0
```

## Note
In the first example, you can partition the array into $$$[6,9]$$$ and $$$[3,12]$$$, so you must remove at least $$$1$$$ element. Removing $$$3$$$ is sufficient.

In the second example, the array is already good, so you don't need to remove any elements.

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
This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array $$$a$$$ of length $$$n$$$ written on it, and then he does the following:

- he picks a range $$$(l, r)$$$ and cuts the subsegment $$$a_l, a_{l + 1}, \ldots, a_r$$$ out, removing the rest of the array.
- he then cuts this range into multiple subranges.
- to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their least common multiple (LCM).

Formally, he partitions the elements of $$$a_l, a_{l + 1}, \ldots, a_r$$$ into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for $$$q$$$ independent ranges $$$(l, r)$$$, tell Baby Ehab the minimum number of subarrays he needs.

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

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

Each of the next $$$q$$$ lines contains $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of this query's interval.

## Output Format
For each query, print its answer on a new line.

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

## Note
The first query asks about the whole array. You can partition it into $$$[2]$$$, $$$[3,10,7]$$$, and $$$[5,14]$$$. The first subrange has product and LCM equal to $$$2$$$. The second has product and LCM equal to $$$210$$$. And the third has product and LCM equal to $$$70$$$. Another possible partitioning is $$$[2,3]$$$, $$$[10,7]$$$, and $$$[5,14]$$$.

The second query asks about the range $$$(2,4)$$$. Its product is equal to its LCM, so you don't need to partition it further.

The last query asks about the range $$$(3,5)$$$. You can partition it into $$$[10,7]$$$ and $$$[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 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
This time around, Baby Ehab will play with permutations. He has $$$n$$$ cubes arranged in a row, with numbers from $$$1$$$ to $$$n$$$ written on them. He'll make exactly $$$j$$$ operations. In each operation, he'll pick up $$$2$$$ cubes and switch their positions.

He's wondering: how many different sequences of cubes can I have at the end? Since Baby Ehab is a turbulent person, he doesn't know how many operations he'll make, so he wants the answer for every possible $$$j$$$ between $$$1$$$ and $$$k$$$.

## Input Format
The only line contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le k \le 200$$$) — the number of cubes Baby Ehab has, and the parameter $$$k$$$ from the statement.

## Output Format
Print $$$k$$$ space-separated integers. The $$$i$$$-th of them is the number of possible sequences you can end up with if you do exactly $$$i$$$ operations. Since this number can be very large, print the remainder when it's divided by $$$10^9+7$$$.

## Examples
```input
2 3
```
```output
1 1 1
```
-----
```input
3 2
```
```output
3 3
```
-----
```input
4 2
```
```output
6 12
```

## Note
In the second example, there are $$$3$$$ sequences he can get after $$$1$$$ swap, because there are $$$3$$$ pairs of cubes he can swap. Also, there are $$$3$$$ sequences he can get after $$$2$$$ swaps:

- $$$[1,2,3]$$$,
- $$$[3,1,2]$$$,
- $$$[2,3,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
Given an integer $$$n$$$, find the maximum value of integer $$$k$$$ such that the following condition holds:

$$$n$$$ & ($$$n-1$$$) & ($$$n-2$$$) & ($$$n-3$$$) & ... ($$$k$$$) = $$$0$$$

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

## Output Format
For each test case, output a single integer — the required integer $$$k$$$.

## Examples
```input
3
2
5
17
```
```output
1
3
15
```

## Note
In the first testcase, the maximum value for which the continuous & operation gives 0 value, is 1.

In the second testcase, the maximum value for which the continuous & operation gives 0 value, is 3. No value greater then 3, say for example 4, will give the & sum 0.

- $$$5 \, \& \, 4 \neq 0$$$,
- $$$5 \, \& \, 4 \, \& \, 3 = 0$$$.

Hence, 3 is the answer.

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 weight of a sequence is defined as the number of unordered pairs of indexes $$$(i,j)$$$ (here $$$i \lt j$$$) with same value ($$$a_{i} = a_{j}$$$). For example, the weight of sequence $$$a = [1, 1, 2, 2, 1]$$$ is $$$4$$$. The set of unordered pairs of indexes with same value are $$$(1, 2)$$$, $$$(1, 5)$$$, $$$(2, 5)$$$, and $$$(3, 4)$$$.

You are given a sequence $$$a$$$ of $$$n$$$ integers. Print the sum of the weight of all subsegments of $$$a$$$.

A sequence $$$b$$$ is a subsegment of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

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

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

## Output Format
For each test case, print a single integer — the sum of the weight of all subsegments of $$$a$$$.

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

## Note
- In test case $$$1$$$, all possible subsegments of sequence $$$[1, 2, 1, 1]$$$ having size more than $$$1$$$ are:   $$$[1, 2]$$$ having $$$0$$$ valid unordered pairs;  $$$[2, 1]$$$ having $$$0$$$ valid unordered pairs;  $$$[1, 1]$$$ having $$$1$$$ valid unordered pair;  $$$[1, 2, 1]$$$ having $$$1$$$ valid unordered pairs;  $$$[2, 1, 1]$$$ having $$$1$$$ valid unordered pair;  $$$[1, 2, 1, 1]$$$ having $$$3$$$ valid unordered pairs.  Answer is $$$6$$$.
- In test case $$$2$$$, all elements of the sequence are distinct. So, there is no valid unordered pair with the same value for any subarray. 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: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ integers. Define the cost of some array $$$t$$$ as follows:

$$$$$$cost(t) = \sum_{x \in set(t) } last(x) - first(x),$$$$$$

where $$$set(t)$$$ is the set of all values in $$$t$$$ without repetitions, $$$first(x)$$$, and $$$last(x)$$$ are the indices of the first and last occurrence of $$$x$$$ in $$$t$$$, respectively. In other words, we compute the distance between the first and last occurrences for each distinct element and sum them up.

You need to split the array $$$a$$$ into $$$k$$$ consecutive segments such that each element of $$$a$$$ belongs to exactly one segment and the sum of the cost of individual segments is minimum.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 35\,000$$$, $$$1 \le k \le \min(n,100)$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

## Output Format
Output the minimum sum of the cost of individual segments.

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

## Note
In the first example, we can divide the array into $$$[1,6,6,4]$$$ and $$$[6,6,6]$$$. Cost of $$$[1,6,6,4]$$$ will be $$$(1-1) + (3 - 2) + (4-4) = 1$$$ and cost of $$$[6,6,6]$$$ will be $$$3-1 = 2$$$. Total cost would be $$$1 + 2 = 3$$$.

In the second example, divide the array into $$$[5,5],[5],[5,2,3]$$$ and $$$[3]$$$. Total Cost would be $$$1 + 0 + 0 + 0 = 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
Gregor is learning about RSA cryptography, and although he doesn't understand how RSA works, he is now fascinated with prime numbers and factoring them.

Gregor's favorite prime number is $$$P$$$. Gregor wants to find two bases of $$$P$$$. Formally, Gregor is looking for two integers $$$a$$$ and $$$b$$$ which satisfy both of the following properties.

- $$$P \bmod a = P \bmod b$$$, where $$$x \bmod y$$$ denotes the remainder when $$$x$$$ is divided by $$$y$$$, and
- $$$2 \le a < b \le P$$$.

Help Gregor find two bases of his favorite prime number!

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

Each subsequent line contains the integer $$$P$$$ ($$$5 \le P \le {10}^9$$$), with $$$P$$$ guaranteed to be prime.

## Output Format
Your output should consist of $$$t$$$ lines. Each line should consist of two integers $$$a$$$ and $$$b$$$ ($$$2 \le a < b \le P$$$). If there are multiple possible solutions, print any.

## Examples
```input
2
17
5
```
```output
3 5
2 4
```

## Note
The first query is $$$P=17$$$. $$$a=3$$$ and $$$b=5$$$ are valid bases in this case, because $$$17 \bmod 3 = 17 \bmod 5 = 2$$$. There are other pairs which work as well.

In the second query, with $$$P=5$$$, the only solution is $$$a=2$$$ 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 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 is a chessboard of size $$$n$$$ by $$$n$$$. The square in the $$$i$$$-th row from top and $$$j$$$-th column from the left is labelled $$$(i,j)$$$.

Currently, Gregor has some pawns in the $$$n$$$-th row. There are also enemy pawns in the $$$1$$$-st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from $$$(i,j)$$$ to $$$(i-1,j)$$$) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from $$$(i,j)$$$ to either $$$(i-1,j-1)$$$ or $$$(i-1,j+1)$$$) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.

Gregor wants to know what is the maximum number of his pawns that can reach row $$$1$$$?

Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor's pawn reaches row $$$1$$$, it is stuck and cannot make any further moves.

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

Each test case consists of three lines. The first line contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot{10}^{5}$$$) — the size of the chessboard.

The second line consists of a string of binary digits of length $$$n$$$, where a $$$1$$$ in the $$$i$$$-th position corresponds to an enemy pawn in the $$$i$$$-th cell from the left, and $$$0$$$ corresponds to an empty cell.

The third line consists of a string of binary digits of length $$$n$$$, where a $$$1$$$ in the $$$i$$$-th position corresponds to a Gregor's pawn in the $$$i$$$-th cell from the left, and $$$0$$$ corresponds to an empty cell.

It is guaranteed that the sum of $$$n$$$ across all test cases is less than $$$2\cdot{10}^{5}$$$.

## Output Format
For each test case, print one integer: the maximum number of Gregor's pawns which can reach the $$$1$$$-st row.

## Examples
```input
4
3
000
111
4
1111
1111
3
010
010
5
11001
00000
```
```output
3
4
0
0
```

## Note
In the first example, Gregor can simply advance all $$$3$$$ of his pawns forward. Thus, the answer is $$$3$$$.

In the second example, Gregor can guarantee that all $$$4$$$ of his pawns reach the enemy row, by following the colored paths as demonstrated in the diagram below. Remember, only Gregor takes turns in this "game"!

In the third example, Gregor's only pawn is stuck behind the enemy pawn, and cannot reach the end.

In the fourth example, Gregor has no pawns, so the answer is clearly $$$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
Polycarp must pay exactly $$$n$$$ burles at the checkout. He has coins of two nominal values: $$$1$$$ burle and $$$2$$$ burles. Polycarp likes both kinds of coins equally. So he doesn't want to pay with more coins of one type than with the other.

Thus, Polycarp wants to minimize the difference between the count of coins of $$$1$$$ burle and $$$2$$$ burles being used. Help him by determining two non-negative integer values $$$c_1$$$ and $$$c_2$$$ which are the number of coins of $$$1$$$ burle and $$$2$$$ burles, respectively, so that the total value of that number of coins is exactly $$$n$$$ (i. e. $$$c_1 + 2 \cdot c_2 = n$$$), and the absolute value of the difference between $$$c_1$$$ and $$$c_2$$$ is as little as possible (i. e. you must minimize $$$|c_1-c_2|$$$).

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

Each test case consists of one line. This line contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the number of burles to be paid by Polycarp.

## Output Format
For each test case, output a separate line containing two integers $$$c_1$$$ and $$$c_2$$$ ($$$c_1, c_2 \ge 0$$$) separated by a space where $$$c_1$$$ is the number of coins of $$$1$$$ burle and $$$c_2$$$ is the number of coins of $$$2$$$ burles. If there are multiple optimal solutions, print any one.

## Examples
```input
6
1000
30
1
32
1000000000
5
```
```output
334 333
10 10
1 0
10 11
333333334 333333333
1 2
```

## Note
The answer for the first test case is "334 333". The sum of the nominal values of all coins is $$$334 \cdot 1 + 333 \cdot 2 = 1000$$$, whereas $$$|334 - 333| = 1$$$. One can't get the better value because if $$$|c_1 - c_2| = 0$$$, then $$$c_1 = c_2$$$ and $$$c_1 \cdot 1 + c_1 \cdot 2 = 1000$$$, but then the value of $$$c_1$$$ isn't an integer.

The answer for the second test case is "10 10". The sum of the nominal values is $$$10 \cdot 1 + 10 \cdot 2 = 30$$$ and $$$|10 - 10| = 0$$$, whereas there's no number having an absolute value less than $$$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
The only difference between this problem and D2 is that you don't have to provide the way to construct the answer in this problem, but you have to do it in D2.

There's a table of $$$n \times m$$$ cells ($$$n$$$ rows and $$$m$$$ columns). The value of $$$n \cdot m$$$ is even.

A domino is a figure that consists of two cells having a common side. It may be horizontal (one of the cells is to the right of the other) or vertical (one of the cells is above the other).

You need to find out whether it is possible to place $$$\frac{nm}{2}$$$ dominoes on the table so that exactly $$$k$$$ of them are horizontal and all the other dominoes are vertical. The dominoes cannot overlap and must fill the whole table.

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

Each test case consists of a single line. The line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n,m \le 100$$$, $$$0 \le k \le \frac{nm}{2}$$$, $$$n \cdot m$$$ is even) — the number of rows, columns and horizontal dominoes, respectively.

## Output Format
For each test case output "YES", if it is possible to place dominoes in the desired way, or "NO" otherwise.

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
8
4 4 2
2 3 0
3 2 3
1 2 0
2 4 2
5 2 2
2 17 16
2 1 1
```
```output
YES
YES
YES
NO
YES
NO
YES
NO
```

Now solve the problem and return the code.