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
Mainak has an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ positive integers. He will do the following operation to this array exactly once:

- Pick a subsegment of this array and cyclically rotate it by any amount.

- Pick two integers $$$l$$$ and $$$r$$$, such that $$$1 \le l \le r \le n$$$, and any positive integer $$$k$$$.
- Repeat this $$$k$$$ times: set $$$a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l$$$ (all changes happen at the same time).

Mainak wants to maximize the value of $$$(a_n - a_1)$$$ after exactly one such operation. Determine the maximum value of $$$(a_n - a_1)$$$ that he can obtain.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 999$$$).

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

## Output Format
For each test case, output a single integer — the maximum value of $$$(a_n - a_1)$$$ that Mainak can obtain by doing the operation exactly once.

## Examples
```input
5
6
1 3 9 11 5 7
1
20
3
9 99 999
4
2 1 8 1
3
2 1 5
```
```output
10
0
990
7
4
```

## Note
- In the first test case, we can rotate the subarray from index $$$3$$$ to index $$$6$$$ by an amount of $$$2$$$ (i.e. choose $$$l = 3$$$, $$$r = 6$$$ and $$$k = 2$$$) to get the optimal array: $$$$$$[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}]$$$$$$ So the answer is $$$a_n - a_1 = 11 - 1 = 10$$$.
- In the second testcase, it is optimal to rotate the subarray starting and ending at index $$$1$$$ and rotating it by an amount of $$$2$$$.
- In the fourth testcase, it is optimal to rotate the subarray starting from index $$$1$$$ to index $$$4$$$ and rotating it by an amount of $$$3$$$. So the answer is $$$8 - 1 = 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
Mainak has two positive integers $$$n$$$ and $$$m$$$.

Mainak finds a sequence $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ positive integers interesting, if for all integers $$$i$$$ ($$$1 \le i \le n$$$), the bitwise XOR of all elements in $$$a$$$ which are strictly less than $$$a_i$$$ is $$$0$$$. Formally if $$$p_i$$$ is the bitwise XOR of all elements in $$$a$$$ which are strictly less than $$$a_i$$$, then $$$a$$$ is an interesting sequence if $$$p_1 = p_2 = \ldots = p_n = 0$$$.

For example, sequences $$$[1,3,2,3,1,2,3]$$$, $$$[4,4,4,4]$$$, $$$[25]$$$ are interesting, whereas $$$[1,2,3,4]$$$ ($$$p_2 = 1 \ne 0$$$), $$$[4,1,1,2,4]$$$ ($$$p_1 = 1 \oplus 1 \oplus 2 = 2 \ne 0$$$), $$$[29,30,30]$$$ ($$$p_2 = 29 \ne 0$$$) aren't interesting.

Here $$$a \oplus b$$$ denotes bitwise XOR of integers $$$a$$$ and $$$b$$$.

Find any interesting sequence $$$a_1, a_2, \ldots, a_n$$$ (or report that there exists no such sequence) such that the sum of the elements in the sequence $$$a$$$ is equal to $$$m$$$, i.e. $$$a_1 + a_2 \ldots + a_n = m$$$.

As a reminder, the bitwise XOR of an empty sequence is considered to be $$$0$$$.

## 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. Description of the test cases follows.

The first line and the only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) — the length of the sequence and the sum of the elements.

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

## Output Format
For each test case, if there exists some interesting sequence, output "Yes" on the first line, otherwise output "No". You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

If the answer is "Yes", output $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \ge 1$$$), forming an interesting sequence such that $$$a_1 + a_2 \ldots + a_n = m$$$. If there are multiple solutions, output any.

## Examples
```input
4
1 3
6 12
2 1
3 6
```
```output
Yes
3
Yes
1 3 2 2 3 1
No
Yes
2 2 2
```

## Note
- In the first test case, $$$[3]$$$ is the only interesting sequence of length $$$1$$$ having sum $$$3$$$.
- In the third test case, there is no sequence of length $$$2$$$ having sum of elements equal to $$$1$$$, so there is no such interesting sequence.
- In the fourth test case, $$$p_1 = p_2 = p_3 = 0$$$, because bitwise XOR of an empty sequence 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Last summer, Feluda gifted Lalmohan-Babu a balanced bracket sequence $$$s$$$ of length $$$2 n$$$.

Topshe was bored during his summer vacations, and hence he decided to draw an undirected graph of $$$2 n$$$ vertices using the balanced bracket sequence $$$s$$$. For any two distinct vertices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le 2 n$$$), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment $$$s[i \ldots j]$$$ forms a balanced bracket sequence.

Determine the number of connected components in Topshe's graph.

See the Notes section for definitions of the underlined terms.

## 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. Description of the test cases follows.

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

The second line of each test case contains a string $$$s$$$ of length $$$2 n$$$ — a balanced bracket sequence consisting of $$$n$$$ opening brackets "(", and $$$n$$$ closing brackets ")".

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

## Output Format
For each test case, output a single integer — the number of connected components in Topshe's graph.

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

## Note
Sample explanation:

In the first test case, the graph constructed from the bracket sequence (), is just a graph containing nodes $$$1$$$ and $$$2$$$ connected by a single edge.

In the second test case, the graph constructed from the bracket sequence ()(()) would be the following (containing two connected components):

Definition of Underlined Terms:

- A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $$$+$$$ and $$$1$$$. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.
- The subsegment $$$s[l \ldots r]$$$ denotes the sequence $$$[s_l, s_{l + 1}, \ldots, s_r]$$$.
- A connected component is a set of vertices $$$X$$$ such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to $$$X$$$ violates this rule.

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 connected, undirected and unweighted graph with $$$n$$$ vertices and $$$m$$$ edges. Notice the limit on the number of edges: $$$m \le n + 2$$$.

Let's say we color some of the edges red and the remaining edges blue. Now consider only the red edges and count the number of connected components in the graph. Let this value be $$$c_1$$$. Similarly, consider only the blue edges and count the number of connected components in the graph. Let this value be $$$c_2$$$.

Find an assignment of colors to the edges such that the quantity $$$c_1+c_2$$$ is minimised.

## 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. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n-1 \leq m \leq \min{\left(n+2,\frac{n \cdot (n-1)}{2}\right)}$$$) — the number of vertices and the number of edges respectively.

$$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$) denoting that the $$$i$$$-th edge goes between vertices $$$u_i$$$ and $$$v_i$$$. The input is guaranteed to have no multiple edges or self loops. The graph is also guaranteed to be connected.

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

## Output Format
For each test case, output a binary string of length $$$m$$$. The $$$i$$$-th character of the string should be 1 if the $$$i$$$-th edge should be colored red, and 0 if it should be colored blue. If there are multiple ways to assign colors to edges that give the minimum answer, you may output any.

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

## Note
- The corresponding graph of the first test case is:  $$$c_1 + c_2 = 1 + 2 = 3$$$
- The corresponding graph of the second test case is:  $$$c_1 + c_2 = 2 + 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation $$$p$$$ of length $$$n$$$ is called almost perfect if for all integer $$$1 \leq i \leq n$$$, it holds that $$$\lvert p_i - p^{-1}_i \rvert \le 1$$$, where $$$p^{-1}$$$ is the inverse permutation of $$$p$$$ (i.e. $$$p^{-1}_{k_1} = k_2$$$ if and only if $$$p_{k_2} = k_1$$$).

Count the number of almost perfect permutations of length $$$n$$$ modulo $$$998244353$$$.

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

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the length of the permutation.

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

## Output Format
For each test case, output a single integer — the number of almost perfect permutations of length $$$n$$$ modulo $$$998244353$$$.

## Examples
```input
3
2
3
50
```
```output
2
4
830690567
```

## Note
For $$$n = 2$$$, both permutations $$$[1, 2]$$$, and $$$[2, 1]$$$ are almost perfect.

For $$$n = 3$$$, there are only $$$6$$$ permutations. Having a look at all of them gives us:

- $$$[1, 2, 3]$$$ is an almost perfect permutation.
- $$$[1, 3, 2]$$$ is an almost perfect permutation.
- $$$[2, 1, 3]$$$ is an almost perfect permutation.
- $$$[2, 3, 1]$$$ is NOT an almost perfect permutation ($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2$$$).
- $$$[3, 1, 2]$$$ is NOT an almost perfect permutation ($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2$$$).
- $$$[3, 2, 1]$$$ is an almost perfect permutation.

So we get $$$4$$$ almost perfect permutations.

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
Mainak has a convex polygon $$$\mathcal P$$$ with $$$n$$$ vertices labelled as $$$A_1, A_2, \ldots, A_n$$$ in a counter-clockwise fashion. The coordinates of the $$$i$$$-th point $$$A_i$$$ are given by $$$(x_i, y_i)$$$, where $$$x_i$$$ and $$$y_i$$$ are both integers.

Further, it is known that the interior angle at $$$A_i$$$ is either a right angle or a proper obtuse angle. Formally it is known that:

- $$$90 ^ \circ \le \angle A_{i - 1}A_{i}A_{i + 1} < 180 ^ \circ$$$, $$$\forall i \in \{1, 2, \ldots, n\}$$$ where we conventionally consider $$$A_0 = A_n$$$ and $$$A_{n + 1} = A_1$$$.

Mainak's friend insisted that all points $$$Q$$$ such that there exists a chord of the polygon $$$\mathcal P$$$ passing through $$$Q$$$ with length not exceeding $$$1$$$, must be coloured $$$\color{red}{\text{red}}$$$.

Mainak wants you to find the area of the coloured region formed by the $$$\color{red}{\text{red}}$$$ points.

Formally, determine the area of the region $$$\mathcal S = \{Q \in \mathcal{P}$$$ | $$$Q \text{ is coloured } \color{red}{\text{red}}\}$$$.

Recall that a chord of a polygon is a line segment between two points lying on the boundary (i.e. vertices or points on edges) of the polygon.

## Input Format
The first line contains an integer $$$n$$$ ($$$4 \le n \le 5000$$$) — the number of vertices of a polygon $$$\mathcal P$$$.

The $$$i$$$-th line of the next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of $$$A_i$$$.

Additional constraint on the input: The vertices form a convex polygon and are listed in counter-clockwise order. It is also guaranteed that all interior angles are in the range $$$[90^\circ ; 180^\circ )$$$.

## Output Format
Print the area of the region coloured in $$$\color{red}{\text{red}}$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

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

## Note
In the first example, the polygon $$$\mathcal P$$$ can be visualised on the Cartesian Plane as:

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
An integer array $$$a_1, a_2, \ldots, a_n$$$ is being transformed into an array of lowercase English letters using the following prodecure:

While there is at least one number in the array:

- Choose any number $$$x$$$ from the array $$$a$$$, and any letter of the English alphabet $$$y$$$.
- Replace all occurrences of number $$$x$$$ with the letter $$$y$$$.

For example, if we initially had an array $$$a = [2, 3, 2, 4, 1]$$$, then we could transform it the following way:

- Choose the number $$$2$$$ and the letter c. After that $$$a = [c, 3, c, 4, 1]$$$.
- Choose the number $$$3$$$ and the letter a. After that $$$a = [c, a, c, 4, 1]$$$.
- Choose the number $$$4$$$ and the letter t. After that $$$a = [c, a, c, t, 1]$$$.
- Choose the number $$$1$$$ and the letter a. After that $$$a = [c, a, c, t, a]$$$.

After the transformation all letters are united into a string, in our example we get the string "cacta".

Having the array $$$a$$$ and the string $$$s$$$ determine if the string $$$s$$$ could be got from the array $$$a$$$ after the described transformation?

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

Then the description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the array $$$a$$$ and the string $$$s$$$.

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

The third line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

## Output Format
For each test case, output "YES", if we can get the string $$$s$$$ from the array $$$a$$$, and "NO" otherwise. You can output each letter in any case.

## Examples
```input
7
5
2 3 2 4 1
cacta
1
50
a
2
11 22
ab
4
1 2 2 1
aaab
5
1 2 3 2 1
aaaaa
6
1 10 2 9 3 8
azzfdb
7
1 2 3 4 1 1 2
abababb
```
```output
YES
YES
YES
NO
YES
YES
NO
```

## Note
The first test case corresponds to the sample described in the statement.

In the second test case we can choose the number $$$50$$$ and the letter a.

In the third test case we can choose the number $$$11$$$ and the letter a, after that $$$a = [a, 22]$$$. Then we choose the number $$$22$$$ and the letter b and get $$$a = [a, b]$$$.

In the fifth test case we can change all numbers one by one to the letter a.

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 $$$n$$$ of integers $$$a_1, a_2, \ldots, a_n$$$. Process $$$q$$$ queries of two types:

- query of the form "0 $$$x_j$$$": add the value $$$x_j$$$ to all even elements of the array $$$a$$$,
- query of the form "1 $$$x_j$$$": add the value $$$x_j$$$ to all odd elements of the array $$$a$$$.

Note that when processing the query, we look specifically at the odd/even value of $$$a_i$$$, not its index.

After processing each query, print the sum of the elements of the array $$$a$$$.

Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

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

The descriptions of the test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n$$$, $$$q \leq 10^5$$$) — the length of array $$$a$$$ and the number of queries.

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

The following $$$q$$$ lines contain queries as two integers $$$type_j$$$ and $$$x_j$$$ $$$(0 \leq type_j \leq 1$$$, $$$1 \leq x_j \leq 10^4$$$).

It is guaranteed that the sum of values $$$n$$$ over all test cases in a test does not exceed $$$10^5$$$. Similarly, the sum of values $$$q$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print $$$q$$$ numbers: the sum of the elements of the array $$$a$$$ after processing a query.

## Examples
```input
4
1 1
1
1 1
3 3
1 2 4
0 2
1 3
0 5
6 7
1 3 2 4 10 48
1 6
0 5
0 4
0 5
1 3
0 12
0 1
6 7
1000000000 1000000000 1000000000 11 15 17
0 17
1 10000
1 51
0 92
0 53
1 16
0 1
```
```output
2
11
14
29
80
100
100
100
118
190
196
3000000094
3000060094
3000060400
3000060952
3000061270
3000061366
3000061366
```

## Note
In the first test case, the array $$$a = [2]$$$ after the first query.

In the third test case, the array $$$a$$$ is modified as follows: $$$[1, 3, 2, 4, 10, 48]$$$ $$$\rightarrow$$$ $$$[7, 9, 2, 4, 10, 48]$$$ $$$\rightarrow$$$ $$$[7, 9, 7, 9, 15, 53]$$$ $$$\rightarrow$$$ $$$[7, 9, 7, 9, 15, 53]$$$ $$$\rightarrow$$$ $$$[10, 12, 10, 12, 18, 56]$$$ $$$\rightarrow$$$ $$$[22, 24, 22, 24, 30, 68]$$$ $$$\rightarrow$$$ $$$[23, 25, 23, 25, 31, 69]$$$.

Now solve the problem and return the code.