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

# Problem
There are three sticks with integer lengths $$$l_1, l_2$$$ and $$$l_3$$$.

You are asked to break exactly one of them into two pieces in such a way that:

- both pieces have positive (strictly greater than $$$0$$$) integer length;
- the total length of the pieces is equal to the original length of the stick;
- it's possible to construct a rectangle from the resulting four sticks such that each stick is used as exactly one of its sides.

A square is also considered a rectangle.

Determine if it's possible to do that.

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

The only line of each testcase contains three integers $$$l_1, l_2, l_3$$$ ($$$1 \le l_i \le 10^8$$$) — the lengths of the sticks.

## Output Format
For each testcase, print "YES" if it's possible to break one of the sticks into two pieces with positive integer length in such a way that it's possible to construct a rectangle from the resulting four sticks. Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as a positive answer).

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

## Note
In the first testcase, the first stick can be broken into parts of length $$$1$$$ and $$$5$$$. We can construct a rectangle with opposite sides of length $$$1$$$ and $$$5$$$.

In the second testcase, breaking the stick of length $$$2$$$ can only result in sticks of lengths $$$1, 1, 2, 5$$$, which can't be made into a rectangle. Breaking the stick of length $$$5$$$ can produce results $$$2, 3$$$ or $$$1, 4$$$ but neither of them can't be put into a rectangle.

In the third testcase, the second stick can be broken into parts of length $$$2$$$ and $$$2$$$. The resulting rectangle has opposite sides $$$2$$$ and $$$2$$$ (which is a square).

In the fourth testcase, the third stick can be broken into parts of length $$$2$$$ and $$$2$$$. The resulting rectangle has opposite sides $$$2$$$ 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 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
You are given an integer array $$$a_1, a_2, \dots, a_n$$$ and integer $$$k$$$.

In one step you can

- either choose some index $$$i$$$ and decrease $$$a_i$$$ by one (make $$$a_i = a_i - 1$$$);
- or choose two indices $$$i$$$ and $$$j$$$ and set $$$a_i$$$ equal to $$$a_j$$$ (make $$$a_i = a_j$$$).

What is the minimum number of steps you need to make the sum of array $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$? (You are allowed to make values of array negative).

## 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 two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{15}$$$) — the size of array $$$a$$$ and upper bound on its sum.

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 itself.

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

## Output Format
For each test case, print one integer — the minimum number of steps to make $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$.

## Examples
```input
4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10
```
```output
10
0
2
7
```

## Note
In the first test case, you should decrease $$$a_1$$$ $$$10$$$ times to get the sum lower or equal to $$$k = 10$$$.

In the second test case, the sum of array $$$a$$$ is already less or equal to $$$69$$$, so you don't need to change it.

In the third test case, you can, for example:

1. set $$$a_4 = a_3 = 1$$$;
2. decrease $$$a_4$$$ by one, and get $$$a_4 = 0$$$.

In the fourth test case, you can, for example:

1. choose $$$a_7$$$ and decrease in by one $$$3$$$ times; you'll get $$$a_7 = -2$$$;
2. choose $$$4$$$ elements $$$a_6$$$, $$$a_8$$$, $$$a_9$$$ and $$$a_{10}$$$ and them equal to $$$a_7 = -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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a binary string (i. e. a string consisting of characters 0 and/or 1) $$$s$$$ of length $$$n$$$. You can perform the following operation with the string $$$s$$$ at most once: choose a substring (a contiguous subsequence) of $$$s$$$ having exactly $$$k$$$ characters 1 in it, and shuffle it (reorder the characters in the substring as you wish).

Calculate the number of different strings which can be obtained from $$$s$$$ by performing this operation at most once.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 5000$$$; $$$0 \le k \le n$$$).

The second line contains the string $$$s$$$ of length $$$n$$$, consisting of characters 0 and/or 1.

## Output Format
Print one integer — the number of different strings which can be obtained from $$$s$$$ by performing the described operation at most once. Since the answer can be large, output it modulo $$$998244353$$$.

## Examples
```input
7 2
1100110
```
```output
16
```
-----
```input
5 0
10010
```
```output
1
```
-----
```input
8 1
10001000
```
```output
10
```
-----
```input
10 8
0010011000
```
```output
1
```

## Note
Some strings you can obtain in the first example:

- to obtain 0110110, you can take the substring from the $$$1$$$-st character to the $$$4$$$-th character, which is 1100, and reorder its characters to get 0110;
- to obtain 1111000, you can take the substring from the $$$3$$$-rd character to the $$$7$$$-th character, which is 00110, and reorder its characters to get 11000;
- to obtain 1100101, you can take the substring from the $$$5$$$-th character to the $$$7$$$-th character, which is 110, and reorder its characters to get 101.

In the second example, $$$k = 0$$$ so you can only choose the substrings consisting only of 0 characters. Reordering them doesn't change the string at all, so the only string you can obtain is 10010.

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

# Problem
Let's call a set of positive integers $$$a_1, a_2, \dots, a_k$$$ quadratic if the product of the factorials of its elements is a square of an integer, i. e. $$$\prod\limits_{i=1}^{k} a_i! = m^2$$$, for some integer $$$m$$$.

You are given a positive integer $$$n$$$.

Your task is to find a quadratic subset of a set $$$1, 2, \dots, n$$$ of maximum size. If there are multiple answers, print any of them.

## Input Format
A single line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

## Output Format
In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.

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

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
Today, Marin is at a cosplay exhibition and is preparing for a group photoshoot!

For the group picture, the cosplayers form a horizontal line. A group picture is considered beautiful if for every contiguous segment of at least $$$2$$$ cosplayers, the number of males does not exceed the number of females (obviously).

Currently, the line has $$$n$$$ cosplayers which can be described by a binary string $$$s$$$. The $$$i$$$-th cosplayer is male if $$$s_i = 0$$$ and female if $$$s_i = 1$$$. To ensure that the line is beautiful, you can invite some additional cosplayers (possibly zero) to join the line at any position. You can't remove any cosplayer from the line.

Marin wants to know the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful. She can't do this on her own, so she's asking you for help. Can you help her?

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

The first line of each test case contains a positive integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of cosplayers in the initial line.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ — describing the cosplayers already in line. Each character of the string is either 0 describing a male, or 1 describing a female.

Note that there is no limit on the sum of $$$n$$$.

## Output Format
For each test case, print the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful.

## Examples
```input
9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101
```
```output
4
2
1
0
2
0
0
0
17
```

## Note
In the first test case, for each pair of adjacent cosplayers, you can invite two female cosplayers to stand in between them. Then, $$$000 \rightarrow 0110110$$$.

In the third test case, you can invite one female cosplayer to stand next to the second cosplayer. Then, $$$010 \rightarrow 0110$$$.

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
Marin wants you to count number of permutations that are beautiful. A beautiful permutation of length $$$n$$$ is a permutation that has the following property: $$$$$$ \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1, $$$$$$ where $$$\gcd$$$ is the greatest common divisor.

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3, 4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n \le 10^3$$$).

## Output Format
For each test case, print one integer — number of beautiful permutations. Because the answer can be very big, please print the answer modulo $$$998\,244\,353$$$.

## Examples
```input
7
1
2
3
4
5
6
1000
```
```output
0
1
0
4
0
36
665702330
```

## Note
In first test case, we only have one permutation which is $$$[1]$$$ but it is not beautiful because $$$\gcd(1 \cdot 1) = 1$$$.

In second test case, we only have one beautiful permutation which is $$$[2, 1]$$$ because $$$\gcd(1 \cdot 2, 2 \cdot 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: 256.0 MB

# Problem
This is the easy version of the problem. The difference in the constraints between both versions is colored below in red. You can make hacks only if all versions of the problem are solved.

Marin and Gojou are playing hide-and-seek with an array.

Gojou initially performs the following steps:

- First, Gojou chooses $$$2$$$ integers $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$.
- Then, Gojou makes an array $$$a$$$ of length $$$r-l+1$$$ which is a permutation of the array $$$[l,l+1,\ldots,r]$$$.
- Finally, Gojou chooses a secret integer $$$x$$$ and sets $$$a_i$$$ to $$$a_i \oplus x$$$ for all $$$i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation).

Marin is then given the values of $$$l,r$$$ and the final array $$$a$$$. She needs to find the secret integer $$$x$$$ to win. Can you help her?

Note that there may be multiple possible $$$x$$$ that Gojou could have chosen. Marin can find any possible $$$x$$$ that could have resulted in the final value of $$$a$$$.

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

In the first line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$ \color{red}{\boldsymbol{0} \boldsymbol{=} \boldsymbol{l}} \le r < 2^{17}$$$).

The second line contains $$$r - l + 1$$$ integers of $$$a_1,a_2,\ldots,a_{r-l+1}$$$ ($$$0 \le a_i < 2^{17}$$$). It is guaranteed that $$$a$$$ can be generated using the steps performed by Gojou.

It is guaranteed that the sum of $$$r - l + 1$$$ over all test cases does not exceed $$$2^{17}$$$.

## Output Format
For each test case print an integer $$$x$$$. If there are multiple answers, print any.

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

## Note
In the first test case, the original array is $$$[3, 2, 1, 0]$$$.

In the second test case, the original array is $$$[0, 3, 2, 1]$$$.

In the third test case, the original array is $$$[2, 1, 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
This is the hard version of the problem. The difference in the constraints between both versions are colored below in red. You can make hacks only if all versions of the problem are solved.

Marin and Gojou are playing hide-and-seek with an array.

Gojou initially perform the following steps:

- First, Gojou chooses $$$2$$$ integers $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$.
- Then, Gojou will make an array $$$a$$$ of length $$$r-l+1$$$ which is a permutation of the array $$$[l,l+1,\ldots,r]$$$.
- Finally, Gojou chooses a secret integer $$$x$$$ and sets $$$a_i$$$ to $$$a_i \oplus x$$$ for all $$$i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation).

Marin is then given the values of $$$l,r$$$ and the final array $$$a$$$. She needs to find the secret integer $$$x$$$ to win. Can you help her?

Note that there may be multiple possible $$$x$$$ that Gojou could have chosen. Marin can find any possible $$$x$$$ that could have resulted in the final value of $$$a$$$.

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

In the first line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$\color{red}{\boldsymbol{0} \boldsymbol{\le} \boldsymbol{l}} \le r < 2^{17}$$$).

The second line contains $$$r - l + 1$$$ space-seperated integers of $$$a_1,a_2,\ldots,a_{r-l+1}$$$ ($$$0 \le a_i < 2^{17}$$$). It is guaranteed that array $$$a$$$ is valid.

It is guaranteed that the sum of $$$r - l + 1$$$ over all test cases does not exceed $$$2^{17}$$$.

## Output Format
For each test case print an integer $$$x$$$. If there are multiple answers, print any.

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

## Note
In the first test case, the original array is $$$[7, 6, 5, 4]$$$.

In the second test case, the original array is $$$[4, 7, 6, 5]$$$.

In the third test case, the original array is $$$[3, 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: 256.0 MB

# Problem
Codeforces separates its users into $$$4$$$ divisions by their rating:

- For Division 1: $$$1900 \leq \mathrm{rating}$$$
- For Division 2: $$$1600 \leq \mathrm{rating} \leq 1899$$$
- For Division 3: $$$1400 \leq \mathrm{rating} \leq 1599$$$
- For Division 4: $$$\mathrm{rating} \leq 1399$$$

Given a $$$\mathrm{rating}$$$, print in which division the $$$\mathrm{rating}$$$ belongs.

## Input Format
The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of testcases.

The description of each test consists of one line containing one integer $$$\mathrm{rating}$$$ ($$$-5000 \leq \mathrm{rating} \leq 5000$$$).

## Output Format
For each test case, output a single line containing the correct division in the format "Division X", where $$$X$$$ is an integer between $$$1$$$ and $$$4$$$ representing the division for the corresponding rating.

## Examples
```input
7
-789
1299
1300
1399
1400
1679
2300
```
```output
Division 4
Division 4
Division 4
Division 4
Division 3
Division 2
Division 1
```

## Note
For test cases $$$1-4$$$, the corresponding ratings are $$$-789$$$, $$$1299$$$, $$$1300$$$, $$$1399$$$, so all of them are in division $$$4$$$.

For the fifth test case, the corresponding rating is $$$1400$$$, so it is in division $$$3$$$.

For the sixth test case, the corresponding rating is $$$1679$$$, so it is in division $$$2$$$.

For the seventh test case, the corresponding rating is $$$2300$$$, so it is in division $$$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 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
Given an array $$$a$$$ of $$$n$$$ elements, print any value that appears at least three times or print -1 if there is no such value.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 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, print any value that appears at least three times or print -1 if there is no such value.

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

## Note
In the first test case there is just a single element, so it can't occur at least three times and the answer is -1.

In the second test case, all three elements of the array are equal to $$$2$$$, so $$$2$$$ occurs three times, and so the answer is $$$2$$$.

For the third test case, $$$2$$$ occurs four times, so the answer is $$$2$$$.

For the fourth test case, $$$4$$$ occurs three times, so the answer is $$$4$$$.

For the fifth test case, $$$1$$$, $$$2$$$ and $$$3$$$ all occur at least three times, so they are all valid outputs.

For the sixth test case, all elements are distinct, so none of them occurs at least three times and the answer is -1.

Now solve the problem and return the code.