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
This is a hard version of the problem. It differs from the easy one only by constraints on $$$n$$$ and $$$t$$$.

There is a deck of $$$n$$$ cards, each of which is characterized by its power. There are two types of cards:

- a hero card, the power of such a card is always equal to $$$0$$$;
- a bonus card, the power of such a card is always positive.

You can do the following with the deck:

- take a card from the top of the deck;
- if this card is a bonus card, you can put it on top of your bonus deck or discard;
- if this card is a hero card, then the power of the top card from your bonus deck is added to his power (if it is not empty), after that the hero is added to your army, and the used bonus discards.

Your task is to use such actions to gather an army with the maximum possible total power.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of cards in the deck.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) — card powers in top-down order.

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

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case — the maximum possible total power of the army that can be achieved.

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

## Note
In the first sample, you can take bonuses $$$1$$$ and $$$2$$$. Both hero cards will receive $$$3$$$ power. If you take all the bonuses, one of them will remain unused.

In the second sample, the hero's card on top of the deck cannot be powered up, and the rest can be powered up with $$$2$$$ and $$$3$$$ bonuses and get $$$6$$$ total power.

In the fourth sample, you can take bonuses $$$1$$$, $$$2$$$, $$$3$$$, $$$5$$$ and skip the bonus $$$6$$$, then the hero $$$4$$$ will be enhanced with a bonus $$$3$$$ by $$$5$$$, and the hero $$$7$$$ with a bonus $$$5$$$ by $$$4$$$. $$$4+5=9$$$.

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

Dmitry decided to remove two consecutive characters from the string $$$s$$$ and you are wondering how many different strings can be obtained after such an operation.

For example, Dmitry has a string "aaabcc". You can get the following different strings: "abcc"(by deleting the first two or second and third characters), "aacc"(by deleting the third and fourth characters),"aaac"(by deleting the fourth and the fifth character) and "aaab" (by deleting the last two).

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

The descriptions of the test cases follow.

The first line of the description of each test case contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

The second line of the description of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters.

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

## Output Format
For each test case print one integer — the number of distinct strings that can be obtained by removing two consecutive letters.

## Examples
```input
7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa
```
```output
4
1
5
3
3
3
1
```

## Note
The first example is explained in the statement.

In the third example, the following strings are obtained: "cdef", "adef", "abef", "abcf", "abcd".

In the seventh example, any deletion will result in the string "aba".

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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Dasha, an excellent student, is studying at the best mathematical lyceum in the country. Recently, a mysterious stranger brought $$$n$$$ words consisting of small latin letters $$$s_1, s_2, \ldots, s_n$$$ to the lyceum. Since that day, Dasha has been tormented by nightmares.

Consider some pair of integers $$$\langle i, j \rangle$$$ ($$$1 \le i \le j \le n$$$). A nightmare is a string for which it is true:

- It is obtained by concatenation $$$s_{i}s_{j}$$$;
- Its length is odd;
- The number of different letters in it is exactly $$$25$$$;
- The number of occurrences of each letter that is in the word is odd.

For example, if $$$s_i=$$$ "abcdefg" and $$$s_j=$$$ "ijklmnopqrstuvwxyz", the pair $$$\langle i, j \rangle$$$ creates a nightmare.

Dasha will stop having nightmares if she counts their number. There are too many nightmares, so Dasha needs your help. Count the number of different nightmares.

Nightmares are called different if the corresponding pairs $$$\langle i, j \rangle$$$ are different. The pairs $$$\langle i_1, j_1 \rangle$$$ and $$$\langle i_2, j_2 \rangle$$$ are called different if $$$i_1 \neq i_2$$$ or $$$j_1 \neq j_2$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of words.

The following $$$n$$$ lines contain the words $$$s_1, s_2, \ldots, s_n$$$, consisting of small latin letters.

It is guaranteed that the total length of words does not exceed $$$5 \cdot 10^6$$$.

## Output Format
Print a single integer — the number of different nightmares.

## Examples
```input
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz
```
```output
5
```

## Note
In the first test, nightmares are created by pairs $$$\langle 1, 3 \rangle$$$, $$$\langle 2, 5 \rangle$$$, $$$\langle 3, 4 \rangle$$$, $$$\langle 6, 7 \rangle$$$, $$$\langle 9, 10 \rangle$$$.

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
Kid was gifted a tree of $$$n$$$ vertices with the root in the vertex $$$1$$$. Since he really like symmetrical objects, Kid wants to find out if this tree is symmetrical.

For example, the trees in the picture above are symmetrical.

And the trees in this picture are not symmetrical.

Formally, a tree is symmetrical if there exists an order of children such that:

- The subtree of the leftmost child of the root is a mirror image of the subtree of the rightmost child;
- the subtree of the second-left child of the root is a mirror image of the subtree of the second-right child of the root;
- ...
- if the number of children of the root is odd, then the subtree of the middle child should be symmetrical.

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

The first line of each case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The following $$$n-1$$$ lines contain two integers each $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — indices of vertices connected by an edge.

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

## Output Format
Output $$$t$$$ strings, each of which is the answer to the corresponding test case. As an answer, output "YES" if this tree is symmetrical, 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
6
6
1 5
1 6
1 2
2 3
2 4
7
1 5
1 3
3 6
1 4
4 7
4 2
9
1 2
2 4
2 3
3 5
1 7
7 6
7 8
8 9
10
2 9
9 10
2 3
6 7
4 3
1 2
3 8
2 5
6 5
10
3 2
8 10
9 7
4 2
8 2
2 1
4 5
6 5
5 7
1
```
```output
YES
NO
YES
NO
NO
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 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
In Berland, there are two types of coins, having denominations of $$$2$$$ and $$$k$$$ burles.

Your task is to determine whether it is possible to represent $$$n$$$ burles in coins, i. e. whether there exist non-negative integers $$$x$$$ and $$$y$$$ such that $$$2 \cdot x + k \cdot y = n$$$.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$; $$$k \ne 2$$$).

## Output Format
For each test case, print YES if it is possible to represent $$$n$$$ burles in coins; otherwise, print NO. You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
4
5 3
6 1
7 4
8 8
```
```output
YES
YES
NO
YES
```

## Note
In the first test case, you can take one coin with denomination $$$2$$$ and one coin with denomination $$$k = 3$$$.

In the second test case, you can take three coins with denomination $$$2$$$. Alternatively, you can take six coins with denomination $$$k = 1$$$.

In the third test case, there is no way to represent $$$7$$$ burles.

In the fourth test case, you can take one coin with denomination $$$k = 8$$$.

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 robot is placed in a cell $$$(0, 0)$$$ of an infinite grid. This robot has adjustable length legs. Initially, its legs have length $$$1$$$.

Let the robot currently be in the cell $$$(x, y)$$$ and have legs of length $$$m$$$. In one move, it can perform one of the following three actions:

- jump into the cell $$$(x + m, y)$$$;
- jump into the cell $$$(x, y + m)$$$;
- increase the length of the legs by $$$1$$$, i. e. set it to $$$m + 1$$$.

What's the smallest number of moves robot has to make to reach a cell $$$(a, b)$$$?

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

The only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$) — the ending cell.

## Output Format
For each test case, print a single integer — the smallest number of moves the robot is required to make to reach a cell $$$(a, b)$$$ from a cell $$$(0, 0)$$$.

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

## Note
In the first testcase, the robot can first jump to $$$(0, 1)$$$, then to $$$(1, 1)$$$. If it ever increases the length of its legs, it will only be able to jump past $$$(1, 1)$$$.

In the second testcase, the robot can jump to $$$(1, 0)$$$, then increase the length of its length to $$$2$$$ and jump three times to reach $$$(1, 6)$$$.

In the third testcase, the robot can increase the length of its legs three times to make it $$$4$$$. Then jump to $$$(0, 4)$$$. Then jump twice to reach $$$(8, 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: 512.0 MB

# Problem
You are given an undirected graph consisting of $$$n$$$ vertices and $$$n-1$$$ edges. The $$$i$$$-th edge has weight $$$a_i$$$; it connects the vertices $$$i$$$ and $$$i+1$$$.

Initially, each vertex contains a chip. Each chip has an integer written on it; the integer written on the chip in the $$$i$$$-th vertex is $$$i$$$.

In one operation, you can choose a chip (if there are multiple chips in a single vertex, you may choose any one of them) and move it along one of the edges of the graph. The cost of this operation is equal to the weight of the edge.

The cost of the graph is the minimum cost of a sequence of such operations that meets the following condition:

- after all operations are performed, each vertex contains exactly one chip, and the integer on each chip is not equal to the index of the vertex where that chip is located.

You are given $$$q$$$ queries of the form:

- $$$k$$$ $$$x$$$ — change the weight of the $$$k$$$-th edge (the one which connects the vertices $$$k$$$ and $$$k+1$$$) to $$$x$$$.

After each query, print the cost of the graph. Note that you don't actually move any chips; when you compute the cost, the chips are on their initial positions.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$).

Then $$$q$$$ lines follow. The $$$i$$$-th of them contains two integers $$$k$$$ and $$$x$$$ ($$$1 \le k \le n-1$$$; $$$1 \le x \le 10^9$$$) for the $$$i$$$-th query.

## Output Format
For each query, print one integer — the cost of the graph after the query is performed.

## Examples
```input
10
12 6 12 15 20 8 17 12 15
8
4 10
7 3
6 14
9 9
2 10
3 5
4 11
7 11
```
```output
126
108
120
108
112
98
98
114
```

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
Vasya lives in a strange world. The year has n months and the i-th month has ai days. Vasya got a New Year present — the clock that shows not only the time, but also the date.

The clock's face can display any number from 1 to d. It is guaranteed that ai ≤ d for all i from 1 to n. The clock does not keep information about the current month, so when a new day comes, it simply increases the current day number by one. The clock cannot display number d + 1, so after day number d it shows day 1 (the current day counter resets). The mechanism of the clock allows you to increase the day number by one manually. When you execute this operation, day d is also followed by day 1.

Vasya begins each day checking the day number on the clock. If the day number on the clock does not match the actual day number in the current month, then Vasya manually increases it by one. Vasya is persistent and repeats this operation until the day number on the clock matches the actual number of the current day in the current month.

A year passed and Vasya wonders how many times he manually increased the day number by one, from the first day of the first month to the last day of the n-th month inclusive, considering that on the first day of the first month the clock display showed day 1.

## Input Format
The first line contains the single number d — the maximum number of the day that Vasya's clock can show (1 ≤ d ≤ 106).

The second line contains a single integer n — the number of months in the year (1 ≤ n ≤ 2000).

The third line contains n space-separated integers: ai (1 ≤ ai ≤ d) — the number of days in each month in the order in which they follow, starting from the first one.

## Output Format
Print a single number — the number of times Vasya manually increased the day number by one throughout the last year.

## Examples
```input
4
2
2 2
```
```output
2
```
-----
```input
5
3
3 4 3
```
```output
3
```
-----
```input
31
12
31 28 31 30 31 30 31 31 30 31 30 31
```
```output
7
```

## Note
In the first sample the situation is like this:

- Day 1. Month 1. The clock shows 1. Vasya changes nothing.
- Day 2. Month 1. The clock shows 2. Vasya changes nothing.
- Day 1. Month 2. The clock shows 3. Vasya manually increases the day number by 1. After that the clock shows 4. Vasya increases the day number by 1 manually. After that the clock shows 1.
- Day 2. Month 2. The clock shows 2. Vasya changes nothing.

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
And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers a1, a2, ..., an. Let's introduce two characteristics for the given array.

- Let's consider an arbitrary interval of the array with length len, starting in position i. Value $$\text{modSum}(i, \text{len}) = \left| \sum_{j=i}^{i+\text{len}-1} a_j \right|$$, is the modular sum on the chosen interval. In other words, the modular sum is the sum of integers on the chosen interval with length len, taken in its absolute value.
- Value $$\max_{1 \leq i \leq n - len + 1} modSum(i, len)$$ is the optimal sum of the array. In other words, the optimal sum of an array is the maximum of all modular sums on various intervals of array with length len.

Your task is to calculate the optimal sum of the given array a. However, before you do the calculations, you are allowed to produce no more than k consecutive operations of the following form with this array: one operation means taking an arbitrary number from array ai and multiply it by -1. In other words, no more than k times you are allowed to take an arbitrary number ai from the array and replace it with  - ai. Each number of the array is allowed to choose an arbitrary number of times.

Your task is to calculate the maximum possible optimal sum of the array after at most k operations described above are completed.

## Input Format
The first line contains two integers n, len (1 ≤ len ≤ n ≤ 105) — the number of elements in the array and the length of the chosen subinterval of the array, correspondingly.

The second line contains a sequence consisting of n integers a1, a2, ..., an (|ai| ≤ 109) — the original array.

The third line contains a single integer k (0 ≤ k ≤ n) — the maximum allowed number of operations.

All numbers in lines are separated by a single space.

## Output Format
In a single line print the maximum possible optimal sum after no more than k acceptable operations are fulfilled.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

## Examples
```input
5 3
0 -2 3 -5 1
2
```
```output
10
```
-----
```input
5 2
1 -3 -10 4 1
3
```
```output
14
```
-----
```input
3 3
-2 -5 4
1
```
```output
11
```

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
Timur loves codeforces. That's why he has a string $$$s$$$ having length $$$10$$$ made containing only lowercase Latin letters. Timur wants to know how many indices string $$$s$$$ differs from the string "codeforces".

For example string $$$s =$$$ "coolforsez" differs from "codeforces" in $$$4$$$ indices, shown in bold.

Help Timur by finding the number of indices where string $$$s$$$ differs from "codeforces".

Note that you can't reorder the characters in the string $$$s$$$.

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

Each test case is one line and contains the string $$$s$$$, consisting of exactly $$$10$$$ lowercase Latin characters.

## Output Format
For each test case, output a single integer — the number of indices where string $$$s$$$ differs.

## Examples
```input
5
coolforsez
cadafurcie
codeforces
paiuforces
forcescode
```
```output
4
5
0
4
9
```

Now solve the problem and return the code.