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

# Problem
Let's call a string good if its length is at least $$$2$$$ and all of its characters are $$$\texttt{A}$$$ except for the last character which is $$$\texttt{B}$$$. The good strings are $$$\texttt{AB},\texttt{AAB},\texttt{AAAB},\ldots$$$. Note that $$$\texttt{B}$$$ is not a good string.

You are given an initially empty string $$$s_1$$$.

You can perform the following operation any number of times:

- Choose any position of $$$s_1$$$ and insert some good string in that position.

Given a string $$$s_2$$$, can we turn $$$s_1$$$ into $$$s_2$$$ after some number of operations?

## Input Format
Each test contains multiple test cases. The first line contains a single 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 a single string $$$s_2$$$ ($$$1 \leq |s_2| \leq 2 \cdot 10^5$$$).

It is guaranteed that $$$s_2$$$ consists of only the characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$.

It is guaranteed that the sum of $$$|s_2|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print "YES" (without quotes) if we can turn $$$s_1$$$ into $$$s_2$$$ after some number of operations, and "NO" (without quotes) otherwise.

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

## Examples
```input
4
AABAB
ABB
AAAAAAAAB
A
```
```output
YES
NO
YES
NO
```

## Note
In the first test case, we transform $$$s_1$$$ as such: $$$\varnothing \to \color{red}{\texttt{AAB}} \to \texttt{A}\color{red}{\texttt{AB}}\texttt{AB}$$$.

In the third test case, we transform $$$s_1$$$ as such: $$$\varnothing \to \color{red}{\texttt{AAAAAAAAB}}$$$.

In the second and fourth test case, it can be shown that it is impossible to turn $$$s_1$$$ into $$$s_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 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
You are given an array $$$a$$$ of length $$$n$$$. We define the equality of the array as the number of indices $$$1 \le i \le n - 1$$$ such that $$$a_i = a_{i + 1}$$$. We are allowed to do the following operation:

- Select two integers $$$i$$$ and $$$x$$$ such that $$$1 \le i \le n - 1$$$ and $$$1 \le x \le 10^9$$$. Then, set $$$a_i$$$ and $$$a_{i + 1}$$$ to be equal to $$$x$$$.

Find the minimum number of operations needed such that the equality of the array is less than or equal to $$$1$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single 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 \le n \le 2 \cdot 10 ^ 5$$$) — the length of array $$$a$$$.

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

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 operations needed.

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

## Note
In the first test case, we can select $$$i=2$$$ and $$$x=2$$$ to form $$$[1, 2, 2, 1, 1]$$$. Then, we can select $$$i=3$$$ and $$$x=3$$$ to form $$$[1, 2, 3, 3, 1]$$$.

In the second test case, we can select $$$i=3$$$ and $$$x=100$$$ to form $$$[2, 1, 100, 100, 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 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
oolimry has an array $$$a$$$ of length $$$n$$$ which he really likes. Today, you have changed his array to $$$b$$$, a permutation of $$$a$$$, to make him sad.

Because oolimry is only a duck, he can only perform the following operation to restore his array:

- Choose two integers $$$i,j$$$ such that $$$1 \leq i,j \leq n$$$.
- Swap $$$b_i$$$ and $$$b_j$$$.

The sadness of the array $$$b$$$ is the minimum number of operations needed to transform $$$b$$$ into $$$a$$$.

Given the array $$$a$$$, find any array $$$b$$$ which is a permutation of $$$a$$$ that has the maximum sadness over all permutations of the array $$$a$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single 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 a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)  — elements of the array $$$a$$$.

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 $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ — describing the array $$$b$$$. If there are multiple answers, you may print any.

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

## Note
In the first test case, the array $$$[1,2]$$$ has sadness $$$1$$$. We can transform $$$[1,2]$$$ into $$$[2,1]$$$ using one operation with $$$(i,j)=(1,2)$$$.

In the second test case, the array $$$[3,3,2,1]$$$ has sadness $$$2$$$. We can transform $$$[3,3,2,1]$$$ into $$$[1,2,3,3]$$$ with two operations with $$$(i,j)=(1,4)$$$ and $$$(i,j)=(2,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 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
oolimry has an array $$$a$$$ of length $$$n$$$ which he really likes. Today, you have changed his array to $$$b$$$, a permutation of $$$a$$$, to make him sad.

Because oolimry is only a duck, he can only perform the following operation to restore his array:

- Choose two integers $$$i,j$$$ such that $$$1 \leq i,j \leq n$$$.
- Swap $$$b_i$$$ and $$$b_j$$$.

The sadness of the array $$$b$$$ is the minimum number of operations needed to transform $$$b$$$ into $$$a$$$.

Given the arrays $$$a$$$ and $$$b$$$, where $$$b$$$ is a permutation of $$$a$$$, determine if $$$b$$$ has the maximum sadness over all permutations of $$$a$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single 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 a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)  — the elements of the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$)  — the elements of the array $$$b$$$.

It is guaranteed that $$$b$$$ is a permutation of $$$a$$$.

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 "AC" (without quotes) if $$$b$$$ has the maximum sadness over all permutations of $$$a$$$, and "WA" (without quotes) otherwise.

## Examples
```input
4
2
2 1
1 2
4
1 2 3 3
3 3 2 1
2
2 1
2 1
4
1 2 3 3
3 2 3 1
```
```output
AC
AC
WA
WA
```

## Note
In the first test case, the array $$$[1,2]$$$ has sadness $$$1$$$. We can transform $$$[1,2]$$$ into $$$[2,1]$$$ using one operation with $$$(i,j)=(1,2)$$$.

In the second test case, the array $$$[3,3,2,1]$$$ has sadness $$$2$$$. We can transform $$$[3,3,2,1]$$$ into $$$[1,2,3,3]$$$ with two operations with $$$(i,j)=(1,4)$$$ and $$$(i,j)=(2,3)$$$ respectively.

In the third test case, the array $$$[2,1]$$$ has sadness $$$0$$$.

In the fourth test case, the array $$$[3,2,3,1]$$$ has sadness $$$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
There is a grid with $$$r$$$ rows and $$$c$$$ columns, where the square on the $$$i$$$-th row and $$$j$$$-th column has an integer $$$a_{i, j}$$$ written on it. Initially, all elements are set to $$$0$$$. We are allowed to do the following operation:

- Choose indices $$$1 \le i \le r$$$ and $$$1 \le j \le c$$$, then replace all values on the same row or column as $$$(i, j)$$$ with the value xor $$$1$$$. In other words, for all $$$a_{x, y}$$$ where $$$x=i$$$ or $$$y=j$$$ or both, replace $$$a_{x, y}$$$ with $$$a_{x, y}$$$ xor $$$1$$$.

You want to form grid $$$b$$$ by doing the above operations a finite number of times. However, some elements of $$$b$$$ are missing and are replaced with '?' instead.

Let $$$k$$$ be the number of '?' characters. Among all the $$$2^k$$$ ways of filling up the grid $$$b$$$ by replacing each '?' with '0' or '1', count the number of grids, that can be formed by doing the above operation a finite number of times, starting from the grid filled with $$$0$$$. As this number can be large, output it modulo $$$998244353$$$.

## Input Format
The first line contains two integers $$$r$$$ and $$$c$$$ ($$$1 \le r, c \le 2000$$$)  — the number of rows and columns of the grid respectively.

The $$$i$$$-th of the next $$$r$$$ lines contain $$$c$$$ characters $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, c}$$$ ($$$b_{i, j} \in \{0, 1, ?\}$$$).

## Output Format
Print a single integer representing the number of ways to fill up grid $$$b$$$ modulo $$$998244353$$$.

## Examples
```input
3 3
?10
1??
010
```
```output
1
```
-----
```input
2 3
000
001
```
```output
0
```
-----
```input
1 1
?
```
```output
2
```
-----
```input
6 9
1101011?0
001101?00
101000110
001011010
0101?01??
00?1000?0
```
```output
8
```

## Note
In the first test case, the only way to fill in the $$$\texttt{?}$$$s is to fill it in as such:

010111010

This can be accomplished by doing a single operation by choosing $$$(i,j)=(2,2)$$$.

In the second test case, it can be shown that there is no sequence of operations that can produce that grid.

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
You have a binary string $$$a$$$ of length $$$n$$$ consisting only of digits $$$0$$$ and $$$1$$$.

You are given $$$q$$$ queries. In the $$$i$$$-th query, you are given two indices $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$.

Let $$$s=a[l,r]$$$. You are allowed to do the following operation on $$$s$$$:

1. Choose two indices $$$x$$$ and $$$y$$$ such that $$$1 \le x \le y \le |s|$$$. Let $$$t$$$ be the substring $$$t = s[x, y]$$$. Then for all $$$1 \le i \le |t| - 1$$$, the condition $$$t_i \neq t_{i+1}$$$ has to hold. Note that $$$x = y$$$ is always a valid substring.
2. Delete the substring $$$s[x, y]$$$ from $$$s$$$.

For each of the $$$q$$$ queries, find the minimum number of operations needed to make $$$s$$$ an empty string.

Note that for a string $$$s$$$, $$$s[l,r]$$$ denotes the subsegment $$$s_l,s_{l+1},\ldots,s_r$$$.

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

The second line contains a binary string $$$a$$$ of length $$$n$$$ ($$$a_i \in \{0, 1\}$$$).

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$)  — representing the substring of each query.

## Output Format
Print $$$q$$$ lines, the $$$i$$$-th line representing the minimum number of operations needed for the $$$i$$$-th query.

## Examples
```input
5 3
11011
2 4
1 5
3 5
```
```output
1
3
2
```
-----
```input
10 3
1001110110
1 10
2 5
5 10
```
```output
4
2
3
```

## Note
In the first test case,

1. The substring is $$$\texttt{101}$$$, so we can do one operation to make the substring empty.
2. The substring is $$$\texttt{11011}$$$, so we can do one operation on $$$s[2, 4]$$$ to make $$$\texttt{11}$$$, then use two more operations to make the substring empty.
3. The substring is $$$\texttt{011}$$$, so we can do one operation on $$$s[1, 2]$$$ to make $$$\texttt{1}$$$, then use one more operation to make the substring empty.

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: 5.0 seconds
Memory limit: 1024.0 MB

# Problem
You have a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$.

You have a strength of $$$s$$$ and will perform the following operation some times:

- Choose an index $$$i$$$ such that $$$1 \leq i \leq |p|$$$ and $$$|i-p_i| \leq s$$$.
- For all $$$j$$$ such that $$$1 \leq j \leq |p|$$$ and $$$p_i<p_j$$$, update $$$p_j$$$ to $$$p_j-1$$$.
- Delete the $$$i$$$-th element from $$$p$$$. Formally, update $$$p$$$ to $$$[p_1,\ldots,p_{i-1},p_{i+1},\ldots,p_n]$$$.

It can be shown that no matter what $$$i$$$ you have chosen, $$$p$$$ will be a permutation of integers from $$$1$$$ to $$$|p|$$$ after all operations.

You want to be able to transform $$$p$$$ into the empty permutation. Find the minimum strength $$$s$$$ that will allow you to do so.

## Input Format
The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$)  — the length of the permutation $$$p$$$.

The second line of input conatains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$)  — the elements of the permutation $$$p$$$.

It is guaranteed that all elements in $$$p$$$ are distinct.

## Output Format
Print the minimum strength $$$s$$$ required.

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

## Note
In the first test case, the minimum $$$s$$$ required is $$$1$$$.

Here is how we can transform $$$p$$$ into the empty permutation with $$$s=1$$$:

- In the first move, you can only choose $$$i=2$$$ as choosing any other value of $$$i$$$ will result in $$$|i-p_i| \leq s$$$ being false. With $$$i=2$$$, $$$p$$$ will be changed to $$$[2,1]$$$.
- In the second move, you choose $$$i=1$$$, then $$$p$$$ will be changed to $$$[1]$$$.
- In the third move, you choose $$$i=1$$$, then $$$p$$$ will be changed to $$$[~]$$$.

It can be shown that with $$$s=0$$$, it is impossible to transform $$$p$$$ into the empty permutation.

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
A ticket is a string consisting of six digits. A ticket is considered lucky if the sum of the first three digits is equal to the sum of the last three digits. Given a ticket, output if it is lucky or not. Note that a ticket can have leading zeroes.

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

The description of each test consists of one line containing one string consisting of six digits.

## Output Format
Output $$$t$$$ lines, each of which contains the answer to the corresponding test case. Output "YES" if the given ticket is lucky, and "NO" 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
5
213132
973894
045207
000000
055776
```
```output
YES
NO
YES
YES
NO
```

## Note
In the first test case, the sum of the first three digits is $$$2 + 1 + 3 = 6$$$ and the sum of the last three digits is $$$1 + 3 + 2 = 6$$$, they are equal so the answer is "YES".

In the second test case, the sum of the first three digits is $$$9 + 7 + 3 = 19$$$ and the sum of the last three digits is $$$8 + 9 + 4 = 21$$$, they are not equal so the answer is "NO".

In the third test case, the sum of the first three digits is $$$0 + 4 + 5 = 9$$$ and the sum of the last three digits is $$$2 + 0 + 7 = 9$$$, they are equal so the answer is "YES".

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 are $$$n$$$ boxes with different quantities of candies in each of them. The $$$i$$$-th box has $$$a_i$$$ candies inside.

You also have $$$n$$$ friends that you want to give the candies to, so you decided to give each friend a box of candies. But, you don't want any friends to get upset so you decided to eat some (possibly none) candies from each box so that all boxes have the same quantity of candies in them. Note that you may eat a different number of candies from different boxes and you cannot add candies to any of the boxes.

What's the minimum total number of candies you have to eat to satisfy the requirements?

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the number of boxes you have.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$) — the quantity of candies in each box.

## Output Format
For each test case, print a single integer denoting the minimum number of candies you have to eat to satisfy the requirements.

## Examples
```input
5
5
1 2 3 4 5
6
1000 1000 5 1000 1000 1000
10
1 2 3 5 1 2 7 9 13 5
3
8 8 8
1
10000000
```
```output
10
4975
38
0
0
```

## Note
For the first test case, you can eat $$$1$$$ candy from the second box, $$$2$$$ candies from the third box, $$$3$$$ candies from the fourth box and $$$4$$$ candies from the fifth box. Now the boxes have $$$[1, 1, 1, 1, 1]$$$ candies in them and you ate $$$0 + 1 + 2 + 3 + 4 = 10$$$ candies in total so the answer is $$$10$$$.

For the second test case, the best answer is obtained by making all boxes contain $$$5$$$ candies in them, thus eating $$$995 + 995 + 0 + 995 + 995 + 995 = 4975$$$ candies in total.

Now solve the problem and return the code.