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
You are given two integers $$$l$$$ and $$$r$$$, where $$$l < r$$$. We will add $$$1$$$ to $$$l$$$ until the result is equal to $$$r$$$. Thus, there will be exactly $$$r-l$$$ additions performed. For each such addition, let's look at the number of digits that will be changed after it.

For example:

- if $$$l=909$$$, then adding one will result in $$$910$$$ and $$$2$$$ digits will be changed;
- if you add one to $$$l=9$$$, the result will be $$$10$$$ and $$$2$$$ digits will also be changed;
- if you add one to $$$l=489999$$$, the result will be $$$490000$$$ and $$$5$$$ digits will be changed.

Changed digits always form a suffix of the result written in the decimal system.

Output the total number of changed digits, if you want to get $$$r$$$ from $$$l$$$, adding $$$1$$$ each time.

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

Each test case is characterized by two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le 10^9$$$).

## Output Format
For each test case, calculate the total number of changed digits if you want to get $$$r$$$ from $$$l$$$, adding one each time.

## Examples
```input
4
1 9
9 10
10 20
1 1000000000
```
```output
8
2
11
1111111110
```

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
Polycarp has $$$x$$$ of red and $$$y$$$ of blue candies. Using them, he wants to make gift sets. Each gift set contains either $$$a$$$ red candies and $$$b$$$ blue candies, or $$$a$$$ blue candies and $$$b$$$ red candies. Any candy can belong to at most one gift set.

Help Polycarp to find the largest number of gift sets he can create.

For example, if $$$x = 10$$$, $$$y = 12$$$, $$$a = 5$$$, and $$$b = 2$$$, then Polycarp can make three gift sets:

- In the first set there will be $$$5$$$ red candies and $$$2$$$ blue candies;
- In the second set there will be $$$5$$$ blue candies and $$$2$$$ red candies;
- In the third set will be $$$5$$$ blue candies and $$$2$$$ red candies.

Note that in this example there is one red candy that Polycarp does not use in any gift set.

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

Each test case consists of a single string containing four integers $$$x$$$, $$$y$$$, $$$a$$$, and $$$b$$$ ($$$1 \le x, y, a, b \le 10^9$$$).

## Output Format
For each test case, output one number — the maximum number of gift sets that Polycarp can make.

## Examples
```input
9
10 12 2 5
1 1 2 2
52 311 13 27
1000000000 1000000000 1 1
1000000000 1 1 1000000000
1 1000000000 1000000000 1
1 2 1 1
7 8 1 2
4 1 2 3
```
```output
3
0
4
1000000000
1
1
1
5
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
You are given a digital clock with $$$n$$$ digits. Each digit shows an integer from $$$0$$$ to $$$9$$$, so the whole clock shows an integer from $$$0$$$ to $$$10^n-1$$$. The clock will show leading zeroes if the number is smaller than $$$10^{n-1}$$$.

You want the clock to show $$$0$$$ with as few operations as possible. In an operation, you can do one of the following:

- decrease the number on the clock by $$$1$$$, or
- swap two digits (you can choose which digits to swap, and they don't have to be adjacent).

Your task is to determine the minimum number of operations needed to make the clock show $$$0$$$.

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

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

The second line of each test case contains a string of $$$n$$$ digits $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \le s_1, s_2, \ldots, s_n \le 9$$$) — the number on the clock.

Note: If the number is smaller than $$$10^{n-1}$$$ the clock will show leading zeroes.

## Output Format
For each test case, print one integer: the minimum number of operations needed to make the clock show $$$0$$$.

## Examples
```input
7
3
007
4
1000
5
00000
3
103
4
2020
9
123456789
30
001678294039710047203946100020
```
```output
7
2
0
5
6
53
115
```

## Note
In the first example, it's optimal to just decrease the number $$$7$$$ times.

In the second example, we can first swap the first and last position and then decrease the number by $$$1$$$.

In the third example, the clock already shows $$$0$$$, so we don't have to perform any operations.

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
You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Array $$$a$$$ contains each odd integer from $$$1$$$ to $$$2n$$$ in an arbitrary order, and array $$$b$$$ contains each even integer from $$$1$$$ to $$$2n$$$ in an arbitrary order.

You can perform the following operation on those arrays:

- choose one of the two arrays
- pick an index $$$i$$$ from $$$1$$$ to $$$n-1$$$
- swap the $$$i$$$-th and the $$$(i+1)$$$-th elements of the chosen array

For two different arrays $$$x$$$ and $$$y$$$ of the same length $$$n$$$, we say that $$$x$$$ is lexicographically smaller than $$$y$$$ if in the first position where $$$x$$$ and $$$y$$$ differ, the array $$$x$$$ has a smaller element than the corresponding element in $$$y$$$.

## 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 first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the arrays.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2n$$$, all $$$a_i$$$ are odd and pairwise distinct) — array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2n$$$, all $$$b_i$$$ are even and pairwise distinct) — array $$$b$$$.

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

## Output Format
For each test case, print one integer: the minimum number of operations needed to make array $$$a$$$ lexicographically smaller than array $$$b$$$.

We can show that an answer always exists.

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

## Note
In the first example, the array $$$a$$$ is already lexicographically smaller than array $$$b$$$, so no operations are required.

In the second example, we can swap $$$5$$$ and $$$3$$$ and then swap $$$2$$$ and $$$4$$$, which results in $$$[3, 5, 1]$$$ and $$$[4, 2, 6]$$$. Another correct way is to swap $$$3$$$ and $$$1$$$ and then swap $$$5$$$ and $$$1$$$, which results in $$$[1, 5, 3]$$$ and $$$[2, 4, 6]$$$. Yet another correct way is to swap $$$4$$$ and $$$6$$$ and then swap $$$2$$$ and $$$6$$$, which results in $$$[5, 3, 1]$$$ and $$$[6, 2, 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 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
Luntik has decided to try singing. He has $$$a$$$ one-minute songs, $$$b$$$ two-minute songs and $$$c$$$ three-minute songs. He wants to distribute all songs into two concerts such that every song should be included to exactly one concert.

He wants to make the absolute difference of durations of the concerts as small as possible. The duration of the concert is the sum of durations of all songs in that concert.

Please help Luntik and find the minimal possible difference in minutes between the concerts durations.

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

Each test case consists of one line containing three integers $$$a, b, c$$$ $$$(1 \le a, b, c \le 10^9)$$$ — the number of one-minute, two-minute and three-minute songs.

## Output Format
For each test case print the minimal possible difference in minutes between the concerts durations.

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

## Note
In the first test case, Luntik can include a one-minute song and a two-minute song into the first concert, and a three-minute song into the second concert. Then the difference will be equal to $$$0$$$.

In the second test case, Luntik can include two one-minute songs and a two-minute song and a three-minute song into the first concert, and two three-minute songs into the second concert. The duration of the first concert will be $$$1 + 1 + 2 + 3 = 7$$$, the duration of the second concert will be $$$6$$$. The difference of them is $$$|7-6| = 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
Luntik came out for a morning stroll and found an array $$$a$$$ of length $$$n$$$. He calculated the sum $$$s$$$ of the elements of the array ($$$s= \sum_{i=1}^{n} a_i$$$). Luntik calls a subsequence of the array $$$a$$$ nearly full if the sum of the numbers in that subsequence is equal to $$$s-1$$$.

Luntik really wants to know the number of nearly full subsequences of the array $$$a$$$. But he needs to come home so he asks you to solve that problem!

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The next $$$2 \cdot t$$$ lines contain descriptions of test cases. The description of each test case consists of two lines.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 60$$$) — the length of the array.

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

## Output Format
For each test case print the number of nearly full subsequences of the array.

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

## Note
In the first test case, $$$s=1+2+3+4+5=15$$$, only $$$(2,3,4,5)$$$ is a nearly full subsequence among all subsequences, the sum in it is equal to $$$2+3+4+5=14=15-1$$$.

In the second test case, there are no nearly full subsequences.

In the third test case, $$$s=1+0=1$$$, the nearly full subsequences are $$$(0)$$$ and $$$()$$$ (the sum of an empty subsequence 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 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
Grandma Capa has decided to knit a scarf and asked Grandpa Sher to make a pattern for it, a pattern is a string consisting of lowercase English letters. Grandpa Sher wrote a string $$$s$$$ of length $$$n$$$.

Grandma Capa wants to knit a beautiful scarf, and in her opinion, a beautiful scarf can only be knit from a string that is a palindrome. She wants to change the pattern written by Grandpa Sher, but to avoid offending him, she will choose one lowercase English letter and erase some (at her choice, possibly none or all) occurrences of that letter in string $$$s$$$.

She also wants to minimize the number of erased symbols from the pattern. Please help her and find the minimum number of symbols she can erase to make string $$$s$$$ a palindrome, or tell her that it's impossible. Notice that she can only erase symbols equal to the one letter she chose.

A string is a palindrome if it is the same from the left to the right and from the right to the left. For example, the strings 'kek', 'abacaba', 'r' and 'papicipap' are palindromes, while the strings 'abb' and 'iq' are not.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The next $$$2 \cdot t$$$ lines contain the description of test cases. The description of each test case consists of two lines.

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

The second line of each test case contains the string $$$s$$$ consisting of $$$n$$$ lowercase English letters.

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 the minimum number of erased symbols required to make the string a palindrome, if it is possible, and $$$-1$$$, if it is impossible.

## Examples
```input
5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky
```
```output
2
-1
0
3
2
```

## Note
In the first test case, you can choose a letter 'a' and erase its first and last occurrences, you will get a string 'bcaacb', which is a palindrome. You can also choose a letter 'b' and erase all its occurrences, you will get a string 'acaaca', which is a palindrome as well.

In the second test case, it can be shown that it is impossible to choose a letter and erase some of its occurrences to get a palindrome.

In the third test case, you don't have to erase any symbols because the string is already 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 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.5 seconds
Memory limit: 512.0 MB

# Problem
This is an easier version of the problem with smaller constraints.

Korney Korneevich dag up an array $$$a$$$ of length $$$n$$$. Korney Korneevich has recently read about the operation bitwise XOR, so he wished to experiment with it. For this purpose, he decided to find all integers $$$x \ge 0$$$ such that there exists an increasing subsequence of the array $$$a$$$, in which the bitwise XOR of numbers is equal to $$$x$$$.

It didn't take a long time for Korney Korneevich to find all such $$$x$$$, and he wants to check his result. That's why he asked you to solve this problem!

A sequence $$$s$$$ is a subsequence of a sequence $$$b$$$ if $$$s$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

A sequence $$$s_1, s_2, \ldots , s_m$$$ is called increasing if $$$s_1 < s_2 < \ldots < s_m$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 500$$$) — the elements of the array $$$a$$$.

## Output Format
In the first line print a single integer $$$k$$$ — the number of found $$$x$$$ values.

In the second line print $$$k$$$ integers in increasing order $$$x_1, x_2, \ldots x_k$$$ ($$$0 \le x_1 < \ldots < x_k$$$) — found $$$x$$$ values.

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

## Note
In the first test case:

- To get value $$$x = 0$$$ it is possible to choose and empty subsequence
- To get value $$$x = 2$$$ it is possible to choose a subsequence $$$[2]$$$
- To get value $$$x = 4$$$ it is possible to choose a subsequence $$$[4]$$$
- To get value $$$x = 6$$$ it is possible to choose a subsequence $$$[2, 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 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.5 seconds
Memory limit: 512.0 MB

# Problem
This is a harder version of the problem with bigger constraints.

Korney Korneevich dag up an array $$$a$$$ of length $$$n$$$. Korney Korneevich has recently read about the operation bitwise XOR, so he wished to experiment with it. For this purpose, he decided to find all integers $$$x \ge 0$$$ such that there exists an increasing subsequence of the array $$$a$$$, in which the bitwise XOR of numbers is equal to $$$x$$$.

It didn't take a long time for Korney Korneevich to find all such $$$x$$$, and he wants to check his result. That's why he asked you to solve this problem!

A sequence $$$s$$$ is a subsequence of a sequence $$$b$$$ if $$$s$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

A sequence $$$s_1, s_2, \ldots , s_m$$$ is called increasing if $$$s_1 < s_2 < \ldots < s_m$$$.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$) — the elements of the array $$$a$$$.

## Output Format
In the first line print a single integer $$$k$$$ — the number of found $$$x$$$ values.

In the second line print $$$k$$$ integers in increasing order $$$x_1, x_2, \ldots x_k$$$ ($$$0 \le x_1 < \ldots < x_k$$$) — found $$$x$$$ values.

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

## Note
In the first test case:

- To get value $$$x = 0$$$ it is possible to choose and empty subsequence
- To get value $$$x = 2$$$ it is possible to choose a subsequence $$$[2]$$$
- To get value $$$x = 4$$$ it is possible to choose a subsequence $$$[4]$$$
- To get value $$$x = 6$$$ it is possible to choose a subsequence $$$[2, 4]$$$

Now solve the problem and return the code.