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
Grigory has $$$n$$$ magic stones, conveniently numbered from $$$1$$$ to $$$n$$$. The charge of the $$$i$$$-th stone is equal to $$$c_i$$$.

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index $$$i$$$, where $$$2 \le i \le n - 1$$$), and after that synchronizes it with neighboring stones. After that, the chosen stone loses its own charge, but acquires the charges from neighboring stones. In other words, its charge $$$c_i$$$ changes to $$$c_i' = c_{i + 1} + c_{i - 1} - c_i$$$.

Andrew, Grigory's friend, also has $$$n$$$ stones with charges $$$t_i$$$. Grigory is curious, whether there exists a sequence of zero or more synchronization operations, which transforms charges of Grigory's stones into charges of corresponding Andrew's stones, that is, changes $$$c_i$$$ into $$$t_i$$$ for all $$$i$$$?

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of magic stones.

The second line contains integers $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \le c_i \le 2 \cdot 10^9$$$) — the charges of Grigory's stones.

The second line contains integers $$$t_1, t_2, \ldots, t_n$$$ ($$$0 \le t_i \le 2 \cdot 10^9$$$) — the charges of Andrew's stones.

## Output Format
If there exists a (possibly empty) sequence of synchronization operations, which changes all charges to the required ones, print "Yes".

Otherwise, print "No".

## Examples
```input
4
7 2 4 12
7 15 10 12
```
```output
Yes
```
-----
```input
3
4 4 4
1 2 3
```
```output
No
```

## Note
In the first example, we can perform the following synchronizations ($$$1$$$-indexed):

- First, synchronize the third stone $$$[7, 2, \mathbf{4}, 12] \rightarrow [7, 2, \mathbf{10}, 12]$$$.
- Then synchronize the second stone: $$$[7, \mathbf{2}, 10, 12] \rightarrow [7, \mathbf{15}, 10, 12]$$$.

In the second example, any operation with the second stone will not change its charge.

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
The tic-tac-toe game is starting on a tree of $$$n$$$ vertices. Some vertices are already colored in white while the remaining are uncolored.

There are two players — white and black. The players make moves alternatively. The white player starts the game. In his turn, a player must select one uncolored vertex and paint it in his color.

The player wins if he paints some path of three vertices in his color. In case all vertices are colored and neither player won, the game ends in a draw.

Could you please find who will win the game or whether it ends as a draw, assuming both players play optimally?

## Input Format
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 50\,000$$$) — the number of test cases. Then descriptions of $$$T$$$ test cases follow.

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

Each of the following $$$n - 1$$$ lines contains integers $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$) denoting an edge of the tree connecting vertices $$$v$$$ and $$$u$$$.

The last line of a test case contains a string of letters 'W' (for white) and 'N' (for not colored) of length $$$n$$$ denoting already colored vertices. Vertexes already colored in white are denoted as 'W'.

It's guaranteed that the given edges form a tree, that there is at least one uncolored vertex and that there is no path of three white vertices.

It's guaranteed that sum of all $$$n$$$ among all test cases is at most $$$5 \cdot 10^5$$$.

## Output Format
For every test case, print either "White", "Draw" or "Black", depending on the result of the game.

## Examples
```input
2
4
1 2
1 3
1 4
NNNW
5
1 2
2 3
3 4
4 5
NNNNN
```
```output
White
Draw
```

## Note
In the first example, vertex $$$4$$$ is already colored in white. The white player can win by coloring the vertex $$$1$$$ in white first and the remaining vertex on his second turn. The process is illustrated with the pictures below.

In the second example, we can show that no player can enforce their victory.

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
Mike decided to teach programming to children in an elementary school. He knows that it is not an easy task to interest children in that age to code. That is why he decided to give each child two sweets.

Mike has $$$n$$$ sweets with sizes $$$a_1, a_2, \ldots, a_n$$$. All his sweets have different sizes. That is, there is no such pair $$$(i, j)$$$ ($$$1 \leq i, j \leq n$$$) such that $$$i \ne j$$$ and $$$a_i = a_j$$$.

Since Mike has taught for many years, he knows that if he gives two sweets with sizes $$$a_i$$$ and $$$a_j$$$ to one child and $$$a_k$$$ and $$$a_p$$$ to another, where $$$(a_i + a_j) \neq (a_k + a_p)$$$, then a child who has a smaller sum of sizes will be upset. That is, if there are two children who have different sums of sweets, then one of them will be upset. Apparently, Mike does not want somebody to be upset.

Mike wants to invite children giving each of them two sweets. Obviously, he can't give one sweet to two or more children. His goal is to invite as many children as he can.

Since Mike is busy preparing to his first lecture in the elementary school, he is asking you to find the maximum number of children he can invite giving each of them two sweets in such way that nobody will be upset.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 1\,000$$$) — the number of sweets Mike has.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the sizes of the sweets. It is guaranteed that all integers are distinct.

## Output Format
Print one integer — the maximum number of children Mike can invite giving each of them two sweets in such way that nobody will be upset.

## Examples
```input
8
1 8 3 11 4 9 2 7
```
```output
3
```
-----
```input
7
3 1 7 11 9 2 12
```
```output
2
```

## Note
In the first example, Mike can give $$$9+2=11$$$ to one child, $$$8+3=11$$$ to another one, and $$$7+4=11$$$ to the third child. Therefore, Mike can invite three children. Note that it is not the only solution.

In the second example, Mike can give $$$3+9=12$$$ to one child and $$$1+11$$$ to another one. Therefore, Mike can invite two children. Note that it is not the only solution.

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
Traveling around the world you noticed that many shop owners raise prices to inadequate values if the see you are a foreigner.

You define inadequate numbers as follows:

- all integers from $$$1$$$ to $$$9$$$ are inadequate;
- for an integer $$$x \ge 10$$$ to be inadequate, it is required that the integer $$$\lfloor x / 10 \rfloor$$$ is inadequate, but that's not the only condition. Let's sort all the inadequate integers. Let $$$\lfloor x / 10 \rfloor$$$ have number $$$k$$$ in this order. Then, the integer $$$x$$$ is inadequate only if the last digit of $$$x$$$ is strictly less than the reminder of division of $$$k$$$ by $$$11$$$.

Here $$$\lfloor x / 10 \rfloor$$$ denotes $$$x/10$$$ rounded down.

Thus, if $$$x$$$ is the $$$m$$$-th in increasing order inadequate number, and $$$m$$$ gives the remainder $$$c$$$ when divided by $$$11$$$, then integers $$$10 \cdot x + 0, 10 \cdot x + 1 \ldots, 10 \cdot x + (c - 1)$$$ are inadequate, while integers $$$10 \cdot x + c, 10 \cdot x + (c + 1), \ldots, 10 \cdot x + 9$$$ are not inadequate.

The first several inadequate integers are $$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 \ldots$$$. After that, since $$$4$$$ is the fourth inadequate integer, $$$40, 41, 42, 43$$$ are inadequate, while $$$44, 45, 46, \ldots, 49$$$ are not inadequate; since $$$10$$$ is the $$$10$$$-th inadequate number, integers $$$100, 101, 102, \ldots, 109$$$ are all inadequate. And since $$$20$$$ is the $$$11$$$-th inadequate number, none of $$$200, 201, 202, \ldots, 209$$$ is inadequate.

You wrote down all the prices you have seen in a trip. Unfortunately, all integers got concatenated in one large digit string $$$s$$$ and you lost the bounds between the neighboring integers. You are now interested in the number of substrings of the resulting string that form an inadequate number. If a substring appears more than once at different positions, all its appearances are counted separately.

## Input Format
The only line contains the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$), consisting only of digits. It is guaranteed that the first digit of $$$s$$$ is not zero.

## Output Format
In the only line print the number of substrings of $$$s$$$ that form an inadequate number.

## Examples
```input
4021
```
```output
6
```
-----
```input
110
```
```output
3
```

## Note
In the first example the inadequate numbers in the string are $$$1, 2, 4, 21, 40, 402$$$.

In the second example the inadequate numbers in the string are $$$1$$$ and $$$10$$$, and $$$1$$$ appears twice (on the first and on the second positions).

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
Alice has a string $$$s$$$. She really likes the letter "a". She calls a string good if strictly more than half of the characters in that string are "a"s. For example "aaabb", "axaa" are good strings, and "baca", "awwwa", "" (empty string) are not.

Alice can erase some characters from her string $$$s$$$. She would like to know what is the longest string remaining after erasing some characters (possibly zero) to get a good string. It is guaranteed that the string has at least one "a" in it, so the answer always exists.

## Input Format
The first line contains a string $$$s$$$ ($$$1 \leq |s| \leq 50$$$) consisting of lowercase English letters. It is guaranteed that there is at least one "a" in $$$s$$$.

## Output Format
Print a single integer, the length of the longest good string that Alice can get after erasing some characters from $$$s$$$.

## Examples
```input
xaxxxxa
```
```output
3
```
-----
```input
aaabaa
```
```output
6
```

## Note
In the first example, it's enough to erase any four of the "x"s. The answer is $$$3$$$ since that is the maximum number of characters that can remain.

In the second example, we don't need to erase any characters.

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
Bob has a string $$$s$$$ consisting of lowercase English letters. He defines $$$s'$$$ to be the string after removing all "a" characters from $$$s$$$ (keeping all other characters in the same order). He then generates a new string $$$t$$$ by concatenating $$$s$$$ and $$$s'$$$. In other words, $$$t=s+s'$$$ (look at notes for an example).

You are given a string $$$t$$$. Your task is to find some $$$s$$$ that Bob could have used to generate $$$t$$$. It can be shown that if an answer exists, it will be unique.

## Input Format
The first line of input contains a string $$$t$$$ ($$$1 \leq |t| \leq 10^5$$$) consisting of lowercase English letters.

## Output Format
Print a string $$$s$$$ that could have generated $$$t$$$. It can be shown if an answer exists, it is unique. If no string exists, print ":(" (without double quotes, there is no space between the characters).

## Examples
```input
aaaaa
```
```output
aaaaa
```
-----
```input
aacaababc
```
```output
:(
```
-----
```input
ababacacbbcc
```
```output
ababacac
```
-----
```input
baba
```
```output
:(
```

## Note
In the first example, we have $$$s = $$$ "aaaaa", and $$$s' = $$$ "".

In the second example, no such $$$s$$$ can work that will generate the given $$$t$$$.

In the third example, we have $$$s = $$$ "ababacac", and $$$s' = $$$ "bbcc", and $$$t = s + s' = $$$ "ababacacbbcc".

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 frog is initially at position $$$0$$$ on the number line. The frog has two positive integers $$$a$$$ and $$$b$$$. From a position $$$k$$$, it can either jump to position $$$k+a$$$ or $$$k-b$$$.

Let $$$f(x)$$$ be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval $$$[0, x]$$$. The frog doesn't need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from $$$0$$$.

Given an integer $$$m$$$, find $$$\sum_{i=0}^{m} f(i)$$$. That is, find the sum of all $$$f(i)$$$ for $$$i$$$ from $$$0$$$ to $$$m$$$.

## Input Format
The first line contains three integers $$$m, a, b$$$ ($$$1 \leq m \leq 10^9, 1 \leq a,b \leq 10^5$$$).

## Output Format
Print a single integer, the desired sum.

## Examples
```input
7 5 3
```
```output
19
```
-----
```input
1000000000 1 2019
```
```output
500000001500000001
```
-----
```input
100 100000 1
```
```output
101
```
-----
```input
6 4 5
```
```output
10
```

## Note
In the first example, we must find $$$f(0)+f(1)+\ldots+f(7)$$$. We have $$$f(0) = 1, f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3, f(6) = 3, f(7) = 8$$$. The sum of these values is $$$19$$$.

In the second example, we have $$$f(i) = i+1$$$, so we want to find $$$\sum_{i=0}^{10^9} i+1$$$.

In the third example, the frog can't make any jumps in any case.

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
You are given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$.

You will perform $$$q$$$ operations. In the $$$i$$$-th operation, you have a symbol $$$s_i$$$ which is either "<" or ">" and a number $$$x_i$$$.

You make a new array $$$b$$$ such that $$$b_j = -a_j$$$ if $$$a_j s_i x_i$$$ and $$$b_j = a_j$$$ otherwise (i.e. if $$$s_i$$$ is '>', then all $$$a_j > x_i$$$ will be flipped). After doing all these replacements, $$$a$$$ is set to be $$$b$$$.

You want to know what your final array looks like after all operations.

## Input Format
The first line contains two integers $$$n,q$$$ ($$$1 \leq n,q \leq 10^5$$$) — the number of integers and the number of queries.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^5 \leq a_i \leq 10^5$$$) — the numbers.

Each of the next $$$q$$$ lines contains a character and an integer $$$s_i, x_i$$$. ($$$s_i \in \{<, >\}, -10^5 \leq x_i \leq 10^5$$$) – the queries.

## Output Format
Print $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ representing the array after all operations.

## Examples
```input
11 3
-5 -4 -3 -2 -1 0 1 2 3 4 5
> 2
> -4
< 5
```
```output
5 4 -3 -2 -1 0 1 2 -3 4 5
```
-----
```input
5 5
0 1 -2 -1 2
< -2
< -1
< 0
< 1
< 2
```
```output
0 -1 2 -1 2
```

## Note
In the first example, the array goes through the following changes:

- Initial: $$$[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]$$$
- $$$> 2$$$: $$$[-5, -4, -3, -2, -1, 0, 1, 2, -3, -4, -5]$$$
- $$$> -4$$$: $$$[-5, -4, 3, 2, 1, 0, -1, -2, 3, -4, -5]$$$
- $$$< 5$$$: $$$[5, 4, -3, -2, -1, 0, 1, 2, -3, 4, 5]$$$

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
You are given a rooted tree with $$$n$$$ nodes, labeled from $$$1$$$ to $$$n$$$. The tree is rooted at node $$$1$$$. The parent of the $$$i$$$-th node is $$$p_i$$$. A leaf is node with no children. For a given set of leaves $$$L$$$, let $$$f(L)$$$ denote the smallest connected subgraph that contains all leaves $$$L$$$.

You would like to partition the leaves such that for any two different sets $$$x, y$$$ of the partition, $$$f(x)$$$ and $$$f(y)$$$ are disjoint.

Count the number of ways to partition the leaves, modulo $$$998244353$$$. Two ways are different if there are two leaves such that they are in the same set in one way but in different sets in the other.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 200\,000$$$) — the number of nodes in the tree.

The next line contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i < i$$$).

## Output Format
Print a single integer, the number of ways to partition the leaves, modulo $$$998244353$$$.

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

## Note
In the first example, the leaf nodes are $$$2,3,4,5$$$. The ways to partition the leaves are in the following image

In the second example, the only leaf is node $$$10$$$ so there is only one partition. Note that node $$$1$$$ is not a leaf.

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
You are planning to build housing on a street. There are $$$n$$$ spots available on the street on which you can build a house. The spots are labeled from $$$1$$$ to $$$n$$$ from left to right. In each spot, you can build a house with an integer height between $$$0$$$ and $$$h$$$.

In each spot, if a house has height $$$a$$$, you can gain $$$a^2$$$ dollars from it.

The city has $$$m$$$ zoning restrictions though. The $$$i$$$-th restriction says that if the tallest house from spots $$$l_i$$$ to $$$r_i$$$ is strictly more than $$$x_i$$$, you must pay a fine of $$$c_i$$$.

You would like to build houses to maximize your profit (sum of dollars gained minus fines). Determine the maximum profit possible.

## Input Format
The first line contains three integers $$$n,h,m$$$ ($$$1 \leq n,h,m \leq 50$$$) — the number of spots, the maximum height, and the number of restrictions, respectively.

Each of the next $$$m$$$ lines contains four integers $$$l_i, r_i, x_i, c_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$0 \leq x_i \leq h$$$, $$$1 \leq c_i \leq 5\,000$$$).

## Output Format
Print a single integer denoting the maximum profit you can make.

## Examples
```input
3 3 3
1 1 1 1000
2 2 3 1000
3 3 2 1000
```
```output
14
```
-----
```input
4 10 2
2 3 8 76
3 4 7 39
```
```output
289
```

## Note
In the first example, it's optimal to build houses with heights $$$[1, 3, 2]$$$. We get a gain of $$$1^2+3^2+2^2 = 14$$$. We don't violate any restrictions, so there are no fees, so the total profit is $$$14 - 0 = 14$$$.

In the second example, it's optimal to build houses with heights $$$[10, 8, 8, 10]$$$. We get a gain of $$$10^2+8^2+8^2+10^2 = 328$$$, and we violate the second restriction for a fee of $$$39$$$, thus the total profit is $$$328-39 = 289$$$. Note that even though there isn't a restriction on building $$$1$$$, we must still limit its height to be at most $$$10$$$.

Now solve the problem and return the code.