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

# Problem
You have an integer array $$$a$$$ of length $$$n$$$. There are two kinds of operations you can make.

- Remove an integer from $$$a$$$. This operation costs $$$c$$$.
- Insert an arbitrary positive integer $$$x$$$ to any position of $$$a$$$ (to the front, to the back, or between any two consecutive elements). This operation costs $$$d$$$.

You want to make the final array a permutation of any positive length. Please output the minimum cost of doing that. Note that you can make the array empty during the operations, but the final array must contain at least one integer.

A permutation of length $$$n$$$ 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
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Their description follows.

The first line of each test case contains three integers $$$n$$$, $$$c$$$, $$$d$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le c,d \le 10^9$$$).

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 $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output in one line the minimum cost to make the final array a permutation.

## Examples
```input
8
3 3 3
1 2 3
5 1 5
1 2 3 5 6
5 2 3
1 1 1 3 3
5 1 10
2 4 6 8 10
6 2 8
7 3 5 4 4 8
4 10 1
1 2 6 7
4 3 3
2 5 8 7
2 1000000000 1
1000000000 1
```
```output
0
2
8
14
20
3
12
999999998
```

## Note
In the first test case, the array is already a permutation, so there's no need for operations.

In the second test case, we can remove numbers $$$5$$$, $$$6$$$ to get the permutation $$$[1,2,3]$$$ in cost $$$2$$$. Note that we can also get a permutation by inserting a number $$$4$$$, but it costs $$$5$$$.

In the third test case, we can just remove all the numbers except for the first number $$$1$$$. It costs $$$8$$$, and the final array is $$$[1]$$$, which is a permutation of length $$$1$$$.

In the fourth test case, we can remove all the numbers except for $$$2$$$, and insert a number $$$1$$$ to the first position. It costs $$$4+10=14$$$, and the final array is $$$[1,2]$$$, which is a permutation of length $$$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: 256.0 MB

# Problem
You are given a multiset $$$S$$$. Initially, $$$S = \{1,2,3, \ldots, n\}$$$.

You will perform the following operation $$$n-1$$$ times.

- Choose the largest number $$$S_{\text{max}}$$$ in $$$S$$$ and the smallest number $$$S_{\text{min}}$$$ in $$$S$$$. Remove the two numbers from $$$S$$$, and add $$$S_{\text{max}} - S_{\text{min}}$$$ into $$$S$$$.

It's easy to show that there will be exactly one number left after $$$n-1$$$ operations. Output that number.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Their description follows.

For each test case, one single line contains a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the initial size of the multiset $$$S$$$.

## Output Format
For each test case, output an integer denoting the only number left after $$$n-1$$$ operations.

## Examples
```input
5
2
4
7
15
177567
```
```output
1
2
2
4
33914
```

## Note
We show how the multiset $$$S$$$ changes for $$$n=4$$$.

- Operation $$$1$$$: $$$S=\{1,2,3,4\}$$$, remove $$$4$$$, $$$1$$$, add $$$3$$$.
- Operation $$$2$$$: $$$S=\{2,3,3\}$$$, remove $$$3$$$, $$$2$$$, add $$$1$$$.
- Operation $$$3$$$: $$$S=\{1,3\}$$$, remove $$$3$$$, $$$1$$$, add $$$2$$$.
- Final: $$$S = \{2\}$$$.

Thus, the answer for $$$n = 4$$$ is $$$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
An integer template is a string consisting of digits and/or question marks.

A positive (strictly greater than $$$0$$$) integer matches the integer template if it is possible to replace every question mark in the template with a digit in such a way that we get the decimal representation of that integer without any leading zeroes.

For example:

- $$$42$$$ matches 4?;
- $$$1337$$$ matches ????;
- $$$1337$$$ matches 1?3?;
- $$$1337$$$ matches 1337;
- $$$3$$$ does not match ??;
- $$$8$$$ does not match ???8;
- $$$1337$$$ does not match 1?7.

You are given an integer template consisting of at most $$$5$$$ characters. Calculate the number of positive (strictly greater than $$$0$$$) integers that match it.

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

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 5$$$) consisting of digits and/or question marks — the integer template for the corresponding test case.

## Output Format
For each test case, print one integer — the number of positive (strictly greater than $$$0$$$) integers that match the template.

## Examples
```input
8
??
?
0
9
03
1??7
?5?
9??99
```
```output
90
9
0
1
0
100
90
100
```

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 a string $$$s$$$, consisting of lowercase Latin letters.

In one operation, you can select several (one or more) positions in it such that no two selected positions are adjacent to each other. Then you remove the letters on the selected positions from the string. The resulting parts are concatenated without changing their order.

What is the smallest number of operations required to make all the letters in $$$s$$$ the same?

## 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 a string $$$s$$$, consisting of lowercase Latin letters. Its length is from $$$1$$$ to $$$2 \cdot 10^5$$$.

The total length of the strings over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the smallest number of operations required to make all the letters in the given string $$$s$$$ the same.

## Examples
```input
5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul
```
```output
1
3
0
2
4
```

## Note
In the first testcase, you can select positions $$$2, 4$$$ and $$$6$$$ and remove the corresponding letters 'b', 'c' and 'b'.

In the third testcase, the letters in the string are already the same, so you don't have to make any operations.

In the fourth testcase, one of the possible solutions in $$$2$$$ operations is the following. You can select positions $$$1, 4, 6$$$ first. The string becomes "bce". Then select positions $$$1$$$ and $$$3$$$. The string becomes "c". All letters in it are the same, since it's just one letter.

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
A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

- bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
- bracket sequences ")(", "(" and ")" are not.

You are given a regular bracket sequence. In one move, you can remove a pair of adjacent brackets such that the left one is an opening bracket and the right one is a closing bracket. Then concatenate the resulting parts without changing the order. The cost of this move is the number of brackets to the right of the right bracket of this pair.

The cost of the regular bracket sequence is the smallest total cost of the moves required to make the sequence empty.

Actually, you are not removing any brackets. Instead, you are given a regular bracket sequence and an integer $$$k$$$. You can perform the following operation at most $$$k$$$ times:

- extract some bracket from the sequence and insert it back at any position (between any two brackets, at the start or at the end; possibly, at the same place it was before).

After all operations are performed, the bracket sequence has to be regular. What is the smallest possible cost of the resulting regular bracket sequence?

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

The first line of each testcase contains a single integer $$$k$$$ ($$$0 \le k \le 5$$$) — the maximum number of operations you can perform.

The second line contains a non-empty regular bracket sequence, it consists only of characters '(' and ')'.

The total length of the regular bracket sequences over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the smallest possible cost of the regular bracket sequence after you perform at most $$$k$$$ operations on it.

## Examples
```input
7
0
()
0
(())
1
(())
5
()
1
(()()(()))
2
((())()(()())((())))
3
((())()(()())((())))
```
```output
0
1
0
0
1
4
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: 256.0 MB

# Problem
There is a beautiful alley with trees in front of a shopping mall. Unfortunately, it has to go to make space for the parking lot.

The trees on the alley all grow in a single line. There are $$$n$$$ spots for trees, index $$$0$$$ is the shopping mall, index $$$n+1$$$ is the road and indices from $$$1$$$ to $$$n$$$ are the spots for trees. Some of them are taken — there grow trees of the same height $$$k$$$. No more than one tree grows in each spot.

When you chop down a tree in the spot $$$x$$$, you can make it fall either left or right. If it falls to the left, it takes up spots from $$$x-k$$$ to $$$x$$$, inclusive. If it falls to the right, it takes up spots from $$$x$$$ to $$$x+k$$$, inclusive.

Let $$$m$$$ trees on the alley grow in some spots $$$x_1, x_2, \dots, x_m$$$. Let an alley be called unfortunate if all $$$m$$$ trees can be chopped down in such a way that:

- no tree falls on the shopping mall or the road;
- each spot is taken up by no more than one fallen tree.

Calculate the number of different unfortunate alleys with $$$m$$$ trees of height $$$k$$$. Two alleys are considered different if there is a spot $$$y$$$ such that a tree grows in $$$y$$$ on the first alley and doesn't grow in $$$y$$$ on the second alley.

Output the number modulo $$$998\,244\,353$$$.

## Input Format
The only line contains three integers $$$n, m$$$ and $$$k$$$ ($$$1 \le m, k \le n \le 3 \cdot 10^5$$$) — the number of spots for the trees, the number of trees and the height of each tree.

## Output Format
Print a single integer — the number of different unfortunate alleys with $$$m$$$ trees of height $$$k$$$, modulo $$$998\,244\,353$$$.

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

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
LuoTianyi gives you a palindrome$$$^{\dagger}$$$ string $$$s$$$, and she wants you to find out the length of the longest non-empty subsequence$$$^{\ddagger}$$$ of $$$s$$$ which is not a palindrome string. If there is no such subsequence, output $$$-1$$$ instead.

$$$^{\dagger}$$$ A palindrome is a string that reads the same backward as forward. For example, strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

$$$^{\ddagger}$$$ A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from $$$b$$$. For example, strings "a", "aaa", "bab" are subsequences of string "abaab", but strings "codeforces", "bbb", "h" are not.

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

The first and the only line of each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 50$$$) consisting of lowercase English letters — the string that LuoTianyi gives you. It's guaranteed that $$$s$$$ is a palindrome string.

## Output Format
For each test case, output a single integer — the length of the longest non-empty subsequence which is not a palindrome string. If there is no such subsequence, output $$$-1$$$.

## Examples
```input
4
abacaba
aaa
codeforcesecrofedoc
lol
```
```output
6
-1
18
2
```

## Note
In the first test case, "abcaba" is a subsequence of "abacaba" as we can delete the third letter of "abacaba" to get "abcaba", and "abcaba" is not a palindrome string. We can prove that "abcaba" is an example of the longest subsequences of "abacaba" that isn't palindrome, so that the answer is $$$6$$$.

In the second test case, we can only get "a" and "aa", but they are all palindrome strings, so the answer is $$$-1$$$.

Now solve the problem and return the code.