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 are given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. The integers are either $$$1$$$ or $$$-1$$$. You have to perform the following operation exactly once on the array $$$a$$$:

- Choose an index $$$i$$$ ($$$1 \leq i < n$$$) and flip the signs of $$$a_i$$$ and $$$a_{i+1}$$$. Here, flipping the sign means $$$-1$$$ will be $$$1$$$ and $$$1$$$ will be $$$-1$$$.

What is the maximum possible value of $$$a_1 + a_2 + \ldots + a_n$$$ after applying the above operation?

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

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

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = 1$$$ or $$$a_i = -1$$$).

The sum of $$$n$$$ over all cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, print the maximum possible sum of the array $$$a$$$ you can get in a separate line.

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

## Note
In the first case, we can choose index $$$4$$$ and flip the signs of $$$a_4$$$ and $$$a_5$$$. After this operation, the sum will be $$$-1+1+1+1+1 = 3$$$. We can't make the sum larger than this.

In the third case, the only option is to choose the index $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two binary strings $$$a$$$ and $$$b$$$ of length $$$n$$$. In each move, the string $$$a$$$ is modified in the following way.

- An index $$$i$$$ ($$$1 \leq i \leq n$$$) is chosen uniformly at random. The character $$$a_i$$$ will be flipped. That is, if $$$a_i$$$ is $$$0$$$, it becomes $$$1$$$, and if $$$a_i$$$ is $$$1$$$, it becomes $$$0$$$.

What is the expected number of moves required to make both strings equal for the first time?

A binary string is a string, in which the character is either $$$\tt{0}$$$ or $$$\tt{1}$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of the strings.

The second line of each test case contains the binary string $$$a$$$ of length $$$n$$$.

The third line of each test case contains the binary string $$$b$$$ of length $$$n$$$.

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

## Output Format
For each test case, output a single line containing the expected number of moves modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Examples
```input
4
1
0
1
2
00
00
4
1000
1110
5
01001
10111
```
```output
1
0
665496254
665496277
```

## Note
In the first test case, index $$$1$$$ is chosen randomly and $$$a_1$$$ is flipped. After the move, the strings $$$a$$$ and $$$b$$$ are equal. The expected number of moves is $$$1$$$.

The strings $$$a$$$ and $$$b$$$ are already equal in the second test case. So, the expected number of moves is $$$0$$$.

The expected number of moves for the third and fourth test cases are $$$\frac{56}{3}$$$ and $$$\frac{125}{3}$$$ respectively.

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
Alperen is standing at the point $$$(0,0)$$$. He is given a string $$$s$$$ of length $$$n$$$ and performs $$$n$$$ moves. The $$$i$$$-th move is as follows:

- if $$$s_i = \texttt{L}$$$, then move one unit left;
- if $$$s_i = \texttt{R}$$$, then move one unit right;
- if $$$s_i = \texttt{U}$$$, then move one unit up;
- if $$$s_i = \texttt{D}$$$, then move one unit down.

If Alperen starts at the center point, he can make the four moves shown.

Alperen's path in the first test case.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the string.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters $$$\texttt{L}$$$, $$$\texttt{R}$$$, $$$\texttt{D}$$$, and $$$\texttt{U}$$$, denoting the moves Alperen makes.

## Output Format
For each test case, output "YES" (without quotes) if Alperen passes the candy, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
7
7
UUURDDL
2
UR
8
RRRUUDDD
3
LLL
4
DUUR
5
RUDLL
11
LLLLDDRUDRD
```
```output
YES
YES
NO
NO
YES
YES
NO
```

## Note
In the first test case, Alperen follows the path $$$$$$(0,0) \overset{\texttt{U}}{\to} (0,1) \overset{\texttt{U}}{\to} (0,2) \overset{\texttt{U}}{\to} (0,3) \overset{\texttt{R}}{\to} (1,3) \overset{\texttt{D}}{\to} (1,2) \overset{\texttt{D}}{\to} \color{green}{\mathbf{(1,1)}} \overset{\texttt{L}}{\to} (0,1).$$$$$$ Note that Alperen doesn't need to end at the candy's location of $$$(1,1)$$$, he just needs to pass it at some point.

In the second test case, Alperen follows the path $$$$$$(0,0) \overset{\texttt{U}}{\to} (0,1) \overset{\texttt{R}}{\to} \color{green}{\mathbf{(1,1)}}.$$$$$$

In the third test case, Alperen follows the path $$$$$$(0,0) \overset{\texttt{R}}{\to} (1,0) \overset{\texttt{R}}{\to} (2,0) \overset{\texttt{R}}{\to} (3,0) \overset{\texttt{U}}{\to} (3,1) \overset{\texttt{U}}{\to} (3,2) \overset{\texttt{D}}{\to} (3,1) \overset{\texttt{D}}{\to} (3,0) \overset{\texttt{D}}{\to} (3,-1).$$$$$$

In the fourth test case, Alperen follows the path $$$$$$(0,0) \overset{\texttt{L}}{\to} (-1,0) \overset{\texttt{L}}{\to} (-2,0) \overset{\texttt{L}}{\to} (-3,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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's denote the $$$f(x)$$$ function for a string $$$x$$$ as the number of distinct characters that the string contains. For example $$$f(\texttt{abc}) = 3$$$, $$$f(\texttt{bbbbb}) = 1$$$, and $$$f(\texttt{babacaba}) = 3$$$.

Given a string $$$s$$$, split it into two non-empty strings $$$a$$$ and $$$b$$$ such that $$$f(a) + f(b)$$$ is the maximum possible. In other words, find the maximum possible value of $$$f(a) + f(b)$$$ such that $$$a + b = s$$$ (the concatenation of string $$$a$$$ and string $$$b$$$ is equal to string $$$s$$$).

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

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

The second line contains the string $$$s$$$, consisting of lowercase English letters.

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

## Output Format
For each test case, output a single integer  — the maximum possible value of $$$f(a) + f(b)$$$ such that $$$a + b = s$$$.

## Examples
```input
5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz
```
```output
2
7
2
10
3
```

## Note
For the first test case, there is only one valid way to split $$$\texttt{aa}$$$ into two non-empty strings $$$\texttt{a}$$$ and $$$\texttt{a}$$$, and $$$f(\texttt{a}) + f(\texttt{a}) = 1 + 1 = 2$$$.

For the second test case, by splitting $$$\texttt{abcabcd}$$$ into $$$\texttt{abc}$$$ and $$$\texttt{abcd}$$$ we can get the answer of $$$f(\texttt{abc}) + f(\texttt{abcd}) = 3 + 4 = 7$$$ which is maximum possible.

For the third test case, it doesn't matter how we split the string, the answer will always be $$$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
Given an array $$$a_1, a_2, \dots, a_n$$$, you need to handle a total of $$$q$$$ updates and queries of two types:

- $$$1$$$ $$$l$$$ $$$r$$$ — for each index $$$i$$$ with $$$l \leq i \leq r$$$, update the value of $$$a_i$$$ to the sum of the digits of $$$a_i$$$.
- $$$2$$$ $$$x$$$ — output $$$a_x$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the size of the array and the number of queries, respectively.

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 next $$$q$$$ lines of each test case are of two forms:

- $$$1$$$ $$$l$$$ $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — it means, for each index $$$i$$$ with $$$l \leq i \leq r$$$, you should update the value of $$$a_i$$$ to the sum of its digits.
- $$$2$$$ $$$x$$$ ($$$1 \leq x \leq n$$$) — it means you should output $$$a_x$$$.

There is at least one query of the second type.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

The sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output the answers of queries of the second type, in the order they are given.

## Examples
```input
3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 1
1
2 1
```
```output
6
15
1434
1
6
7
36
1
1
```

## Note
In the first test case, the following process occurs:

- Initially, $$$a = [1, 420, 69, 1434, 2023]$$$.
- The operation is performed for $$$l=2$$$, $$$r=3$$$, yielding $$$[1, \color{red}{6}, \color{red}{15}, 1434, 2023]$$$.
- We are queried for $$$x=2$$$, $$$x=3$$$, and $$$x=4$$$, and output $$$6$$$, $$$15$$$, and $$$1434$$$.
- The operation is performed for $$$l=2$$$, $$$r=5$$$, yielding $$$[1, \color{red}{6}, \color{red}{6}, \color{red}{12}, \color{red}{7}]$$$.
- We are queried for $$$x=1$$$, $$$x=3$$$, and $$$x=5$$$, and output $$$1$$$, $$$6$$$, and $$$7$$$.

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
The only difference between the easy and hard versions are the locations you can teleport to.

Consider the points $$$0,1,\dots,n+1$$$ on the number line. There is a teleporter located on each of the points $$$1,2,\dots,n$$$. At point $$$i$$$, you can do the following:

- Move left one unit: it costs $$$1$$$ coin.
- Move right one unit: it costs $$$1$$$ coin.
- Use a teleporter at point $$$i$$$, if it exists: it costs $$$a_i$$$ coins. As a result, you can choose whether to teleport to point $$$0$$$ or point $$$n+1$$$. Once you use a teleporter, you can't use it again.

You have $$$c$$$ coins, and you start at point $$$0$$$. What's the most number of teleporters you can use?

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \leq n \leq 2\cdot10^5$$$; $$$1 \leq c \leq 10^9$$$)  — the length of the array and the number of coins you have respectively.

The following line contains $$$n$$$ space-separated positive integers $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the costs to use the teleporters.

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

## Output Format
For each test case, output the maximum number of teleporters you can use.

## Examples
```input
10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000
```
```output
2
3
0
1
3
2
1
1
2
2
```

## Note
In the first test case, you can move one unit to the right, use the teleporter at index $$$1$$$ and teleport to point $$$n+1$$$, move one unit to the left and use the teleporter at index $$$5$$$. You are left with $$$6-1-1-1-1 = 2$$$ coins, and wherever you teleport, you won't have enough coins to use another teleporter. You have used two teleporters, so the answer is two.

In the second test case, you go four units to the right and use the teleporter to go to $$$n+1$$$, then go three units left and use the teleporter at index $$$6$$$ to go to $$$n+1$$$, and finally, you go left four times and use the teleporter. The total cost will be $$$4+6+3+4+4+9 = 30$$$, and you used three teleporters.

In the third test case, you don't have enough coins to use any teleporter, so the answer is zero.

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

# Problem
In one one-dimensional world there are n platforms. Platform with index k (platforms are numbered from 1) is a segment with coordinates [(k - 1)m, (k - 1)m + l], and l < m. Grasshopper Bob starts to jump along the platforms from point 0, with each jump he moves exactly d units right. Find out the coordinate of the point, where Bob will fall down. The grasshopper falls down, if he finds himself not on the platform, but if he finds himself on the edge of the platform, he doesn't fall down.

## Input Format
The first input line contains 4 integer numbers n, d, m, l (1 ≤ n, d, m, l ≤ 106, l < m) — respectively: amount of platforms, length of the grasshopper Bob's jump, and numbers m and l needed to find coordinates of the k-th platform: [(k - 1)m, (k - 1)m + l].

## Output Format
Output the coordinates of the point, where the grosshopper will fall down. Don't forget that if Bob finds himself on the platform edge, he doesn't fall down.

## Examples
```input
2 2 5 3
```
```output
4
```
-----
```input
5 4 11 8
```
```output
20
```

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

# Problem
Once Bob took a paper stripe of n squares (the height of the stripe is 1 square). In each square he wrote an integer number, possibly negative. He became interested in how many ways exist to cut this stripe into two pieces so that the sum of numbers from one piece is equal to the sum of numbers from the other piece, and each piece contains positive integer amount of squares. Would you help Bob solve this problem?

## Input Format
The first input line contains integer n (1 ≤ n ≤ 105) — amount of squares in the stripe. The second line contains n space-separated numbers — they are the numbers written in the squares of the stripe. These numbers are integer and do not exceed 10000 in absolute value.

## Output Format
Output the amount of ways to cut the stripe into two non-empty pieces so that the sum of numbers from one piece is equal to the sum of numbers from the other piece. Don't forget that it's allowed to cut the stripe along the squares' borders only.

## Examples
```input
9
1 5 -6 7 9 -16 0 -2 2
```
```output
3
```
-----
```input
3
1 1 1
```
```output
0
```
-----
```input
2
0 0
```
```output
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: 2.0 seconds
Memory limit: 128.0 MB

# Problem
According to a new ISO standard, a flag of every country should have, strangely enough, a chequered field n × m, each square should be wholly painted one of 26 colours. The following restrictions are set:

- In each row at most two different colours can be used.
- No two adjacent squares can be painted the same colour.

Pay attention, please, that in one column more than two different colours can be used.

Berland's government took a decision to introduce changes into their country's flag in accordance with the new standard, at the same time they want these changes to be minimal. By the given description of Berland's flag you should find out the minimum amount of squares that need to be painted different colour to make the flag meet the new ISO standard. You are as well to build one of the possible variants of the new Berland's flag.

## Input Format
The first input line contains 2 integers n and m (1 ≤ n, m ≤ 500) — amount of rows and columns in Berland's flag respectively. Then there follows the flag's description: each of the following n lines contains m characters. Each character is a letter from a to z, and it stands for the colour of the corresponding square.

## Output Format
In the first line output the minimum amount of squares that need to be repainted to make the flag meet the new ISO standard. The following n lines should contain one of the possible variants of the new flag. Don't forget that the variant of the flag, proposed by you, should be derived from the old flag with the minimum amount of repainted squares. If the answer isn't unique, output any.

## Examples
```input
3 4
aaaa
bbbb
cccc
```
```output
6
abab
baba
acac
```
-----
```input
3 3
aba
aba
zzz
```
```output
4
aba
bab
zbz
```

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
Patrick has just finished writing a message to his sweetheart Stacey when he noticed that the message didn't look fancy. Patrick was nervous while writing the message, so some of the letters there were lowercase and some of them were uppercase.

Patrick believes that a message is fancy if any uppercase letter stands to the left of any lowercase one. In other words, this rule describes the strings where first go zero or more uppercase letters, and then — zero or more lowercase letters.

To make the message fancy, Patrick can erase some letter and add the same letter in the same place in the opposite case (that is, he can replace an uppercase letter with the lowercase one and vice versa). Patrick got interested in the following question: what minimum number of actions do we need to make a message fancy? Changing a letter's case in the message counts as one action. Patrick cannot perform any other actions.

## Input Format
The only line of the input contains a non-empty string consisting of uppercase and lowercase letters. The string's length does not exceed 105.

## Output Format
Print a single number — the least number of actions needed to make the message fancy.

## Examples
```input
PRuvetSTAaYA
```
```output
5
```
-----
```input
OYPROSTIYAOPECHATALSYAPRIVETSTASYA
```
```output
0
```
-----
```input
helloworld
```
```output
0
```

Now solve the problem and return the code.