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

# Problem
You are given a set of $$$n$$$ points in a 2D plane. No three points are collinear.

A pentagram is a set of $$$5$$$ points $$$A,B,C,D,E$$$ that can be arranged as follows.  Note the length of the line segments don't matter, only that those particular intersections exist.

Count the number of ways to choose $$$5$$$ points from the given set that form a pentagram.

## Input Format
The first line contains an integer $$$n$$$ ($$$5 \leq n \leq 300$$$) — the number of points.

Each of the next $$$n$$$ lines contains two integers $$$x_i, y_i$$$ ($$$-10^6 \leq x_i,y_i \leq 10^6$$$) — the coordinates of the $$$i$$$-th point. It is guaranteed that no three points are collinear.

## Output Format
Print a single integer, the number of sets of $$$5$$$ points that form a pentagram.

## Examples
```input
5
0 0
0 2
2 0
2 2
1 3
```
```output
1
```
-----
```input
5
0 0
4 0
0 4
4 4
2 3
```
```output
0
```
-----
```input
10
841746 527518
595261 331297
-946901 129987
670374 -140388
-684770 309555
-302589 415564
-387435 613331
-624940 -95922
945847 -199224
24636 -565799
```
```output
85
```

## Note
A picture of the first sample:  A picture of the second sample:  A picture of the third sample:

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
Nauuo is a girl who loves writing comments.

One day, she posted a comment on Codeforces, wondering whether she would get upvotes or downvotes.

It's known that there were $$$x$$$ persons who would upvote, $$$y$$$ persons who would downvote, and there were also another $$$z$$$ persons who would vote, but you don't know whether they would upvote or downvote. Note that each of the $$$x+y+z$$$ people would vote exactly one time.

There are three different results: if there are more people upvote than downvote, the result will be "+"; if there are more people downvote than upvote, the result will be "-"; otherwise the result will be "0".

Because of the $$$z$$$ unknown persons, the result may be uncertain (i.e. there are more than one possible results). More formally, the result is uncertain if and only if there exist two different situations of how the $$$z$$$ persons vote, that the results are different in the two situations.

Tell Nauuo the result or report that the result is uncertain.

## Input Format
The only line contains three integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$0\le x,y,z\le100$$$), corresponding to the number of persons who would upvote, downvote or unknown.

## Output Format
If there is only one possible result, print the result : "+", "-" or "0".

Otherwise, print "?" to report that the result is uncertain.

## Examples
```input
3 7 0
```
```output
-
```
-----
```input
2 0 1
```
```output
+
```
-----
```input
1 1 0
```
```output
0
```
-----
```input
0 0 1
```
```output
?
```

## Note
In the first example, Nauuo would definitely get three upvotes and seven downvotes, so the only possible result is "-".

In the second example, no matter the person unknown downvotes or upvotes, Nauuo would get more upvotes than downvotes. So the only possible result is "+".

In the third example, Nauuo would definitely get one upvote and one downvote, so the only possible result is "0".

In the fourth example, if the only one person upvoted, the result would be "+", otherwise, the result would be "-". There are two possible results, so the result is uncertain.

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
Nauuo is a girl who loves playing chess.

One day she invented a game by herself which needs $$$n$$$ chess pieces to play on a $$$m\times m$$$ chessboard. The rows and columns are numbered from $$$1$$$ to $$$m$$$. We denote a cell on the intersection of the $$$r$$$-th row and $$$c$$$-th column as $$$(r,c)$$$.

The game's goal is to place $$$n$$$ chess pieces numbered from $$$1$$$ to $$$n$$$ on the chessboard, the $$$i$$$-th piece lies on $$$(r_i,\,c_i)$$$, while the following rule is satisfied: for all pairs of pieces $$$i$$$ and $$$j$$$, $$$|r_i-r_j|+|c_i-c_j|\ge|i-j|$$$. Here $$$|x|$$$ means the absolute value of $$$x$$$.

However, Nauuo discovered that sometimes she couldn't find a solution because the chessboard was too small.

She wants to find the smallest chessboard on which she can put $$$n$$$ pieces according to the rules.

She also wonders how to place the pieces on such a chessboard. Can you help her?

## Input Format
The only line contains a single integer $$$n$$$ ($$$1\le n\le 1000$$$) — the number of chess pieces for the game.

## Output Format
The first line contains a single integer — the minimum value of $$$m$$$, where $$$m$$$ is the length of sides of the suitable chessboard.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$r_i$$$ and $$$c_i$$$ ($$$1\le r_i,c_i\le m$$$) — the coordinates of the $$$i$$$-th chess piece.

If there are multiple answers, print any.

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

## Note
In the first example, you can't place the two pieces on a $$$1\times1$$$ chessboard without breaking the rule. But you can place two pieces on a $$$2\times2$$$ chessboard like this:

In the second example, you can't place four pieces on a $$$2\times2$$$ chessboard without breaking the rule. For example, if you place the pieces like this:

then $$$|r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1$$$, $$$|1-3|=2$$$, $$$1<2$$$; and $$$|r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2$$$, $$$|1-4|=3$$$, $$$2<3$$$. It doesn't satisfy the rule.

However, on a $$$3\times3$$$ chessboard, you can place four pieces like this:

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 given integer $$$n$$$. Find the number of ways to fill all $$$3 \times n$$$ tiles with the shape described in the picture below. Upon filling, no empty spaces are allowed. Shapes cannot overlap.

This picture describes when $$$n = 4$$$. The left one is the shape and the right one is $$$3 \times n$$$ tiles.

## Input Format
The only line contains one integer $$$n$$$ ($$$1 \le n \le 60$$$) — the length.

## Output Format
Print the number of ways to fill.

## Examples
```input
4
```
```output
4
```
-----
```input
1
```
```output
0
```

## Note
In the first example, there are $$$4$$$ possible cases of filling.

In the second example, you cannot fill the shapes in $$$3 \times 1$$$ tiles.

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 given picture with size $$$w \times h$$$. Determine if the given picture has a single "+" shape or not. A "+" shape is described below:

- A "+" shape has one center nonempty cell.
- There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction.
- All other cells are empty.

Find out if the given picture has single "+" shape.

## Input Format
The first line contains two integers $$$h$$$ and $$$w$$$ ($$$1 \le h$$$, $$$w \le 500$$$) — the height and width of the picture.

The $$$i$$$-th of the next $$$h$$$ lines contains string $$$s_{i}$$$ of length $$$w$$$ consisting "." and "*" where "." denotes the empty space and "*" denotes the non-empty space.

## Output Format
If the given picture satisfies all conditions, print "YES". Otherwise, print "NO".

You can output each letter in any case (upper or lower).

## Examples
```input
5 6
......
..*...
.****.
..*...
..*...
```
```output
YES
```
-----
```input
3 5
..*..
****.
.*...
```
```output
NO
```
-----
```input
7 7
.......
...*...
..****.
...*...
...*...
.......
.*.....
```
```output
NO
```
-----
```input
5 6
..**..
..**..
******
..**..
..**..
```
```output
NO
```
-----
```input
3 7
.*...*.
***.***
.*...*.
```
```output
NO
```
-----
```input
5 10
..........
..*.......
.*.******.
..*.......
..........
```
```output
NO
```

## Note
In the first example, the given picture contains one "+".

In the second example, two vertical branches are located in a different column.

In the third example, there is a dot outside of the shape.

In the fourth example, the width of the two vertical branches is $$$2$$$.

In the fifth example, there are two shapes.

In the sixth example, there is an empty space inside of the shape.

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 given tree consist of $$$n$$$ vertices. Select a vertex as root vertex that satisfies the condition below.

- For all vertices $$$v_{1}$$$ and $$$v_{2}$$$, if $$$distance$$$($$$root$$$, $$$v_{1}$$$) $$$= distance$$$($$$root$$$, $$$v_{2})$$$ then $$$degree$$$($$$v_{1}$$$) $$$= degree$$$($$$v_{2}$$$), where $$$degree$$$ means the number of vertices connected to that vertex, and $$$distance$$$ means the number of edges between two vertices.

Determine and find if there is such root vertex in the tree. If there are multiple answers, find any of them.

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

Each of the next $$$n-1$$$ lines contains two integers $$$v_{i}$$$ and $$$u_{i}$$$ ($$$1 \le v_{i} \lt u_{i} \le n$$$) — it means there is an edge exist between $$$v_{i}$$$ and $$$u_{i}$$$. It is guaranteed that the graph forms tree.

## Output Format
If there is such root vertex exists, print any of them. Otherwise, print $$$-1$$$.

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

## Note
This is the picture for the first example. $$$1$$$, $$$5$$$, $$$7$$$ also can be a valid answer.

This is the picture for the second example. You can see that it's impossible to find such root vertex.

Now solve the problem and return the code.