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
A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular (shortly, RBS) if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are RBS and ")(" and "(()" are not.

We can see that each opening bracket in RBS is paired with some closing bracket, and, using this fact, we can define nesting depth of the RBS as maximum number of bracket pairs, such that the $$$2$$$-nd pair lies inside the $$$1$$$-st one, the $$$3$$$-rd one — inside the $$$2$$$-nd one and so on. For example, nesting depth of "" is $$$0$$$, "()()()" is $$$1$$$ and "()((())())" is $$$3$$$.

Now, you are given RBS $$$s$$$ of even length $$$n$$$. You should color each bracket of $$$s$$$ into one of two colors: red or blue. Bracket sequence $$$r$$$, consisting only of red brackets, should be RBS, and bracket sequence, consisting only of blue brackets $$$b$$$, should be RBS. Any of them can be empty. You are not allowed to reorder characters in $$$s$$$, $$$r$$$ or $$$b$$$. No brackets can be left uncolored.

Among all possible variants you should choose one that minimizes maximum of $$$r$$$'s and $$$b$$$'s nesting depth. If there are multiple solutions you can print any of them.

## Input Format
The first line contains an even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of RBS $$$s$$$.

The second line contains regular bracket sequence $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{$$$"(", ")"$$$\}$$$).

## Output Format
Print single string $$$t$$$ of length $$$n$$$ consisting of "0"-s and "1"-s. If $$$t_i$$$ is equal to 0 then character $$$s_i$$$ belongs to RBS $$$r$$$, otherwise $$$s_i$$$ belongs to $$$b$$$.

## Examples
```input
2
()
```
```output
11
```
-----
```input
4
(())
```
```output
0101
```
-----
```input
10
((()())())
```
```output
0110001111
```

## Note
In the first example one of optimal solutions is $$$s = $$$ "$$$\color{blue}{()}$$$". $$$r$$$ is empty and $$$b = $$$ "$$$()$$$". The answer is $$$\max(0, 1) = 1$$$.

In the second example it's optimal to make $$$s = $$$ "$$$\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}$$$". $$$r = b = $$$ "$$$()$$$" and the answer is $$$1$$$.

In the third example we can make $$$s = $$$ "$$$\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}$$$". $$$r = $$$ "$$$()()$$$" and $$$b = $$$ "$$$(()())$$$" and the answer is $$$2$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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 an array consisting of $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ and an integer $$$x$$$. It is guaranteed that for every $$$i$$$, $$$1 \le a_i \le x$$$.

Let's denote a function $$$f(l, r)$$$ which erases all values such that $$$l \le a_i \le r$$$ from the array $$$a$$$ and returns the resulting array. For example, if $$$a = [4, 1, 1, 4, 5, 2, 4, 3]$$$, then $$$f(2, 4) = [1, 1, 5]$$$.

Your task is to calculate the number of pairs $$$(l, r)$$$ such that $$$1 \le l \le r \le x$$$ and $$$f(l, r)$$$ is sorted in non-descending order. Note that the empty array is also considered sorted.

## Input Format
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n, x \le 10^6$$$) — the length of array $$$a$$$ and the upper limit for its elements, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le x$$$).

## Output Format
Print the number of pairs $$$1 \le l \le r \le x$$$ such that $$$f(l, r)$$$ is sorted in non-descending order.

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

## Note
In the first test case correct pairs are $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$.

In the second test case correct pairs are $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 3)$$$ and $$$(3, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a_1, a_2, \dots, a_n$$$. All $$$a_i$$$ are pairwise distinct.

Let's define function $$$f(l, r)$$$ as follows:

- let's define array $$$b_1, b_2, \dots, b_{r - l + 1}$$$, where $$$b_i = a_{l - 1 + i}$$$;
- sort array $$$b$$$ in increasing order;
- result of the function $$$f(l, r)$$$ is $$$\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$$$.

Calculate $$$\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$$$, i.e. total sum of $$$f$$$ for all subsegments of $$$a$$$ modulo $$$10^9+7$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$) — array $$$a$$$.

## Output Format
Print one integer — the total sum of $$$f$$$ for all subsegments of $$$a$$$ modulo $$$10^9+7$$$

## Examples
```input
4
5 2 4 7
```
```output
167
```
-----
```input
3
123456789 214365879 987654321
```
```output
582491518
```

## Note
Description of the first example:

- $$$f(1, 1) = 5 \cdot 1 = 5$$$;
- $$$f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$$$;
- $$$f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$$$;
- $$$f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$$$;
- $$$f(2, 2) = 2 \cdot 1 = 2$$$;
- $$$f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$$$;
- $$$f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$$$;
- $$$f(3, 3) = 4 \cdot 1 = 4$$$;
- $$$f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$$$;
- $$$f(4, 4) = 7 \cdot 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
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 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
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 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 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 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 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 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 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.
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
Let $$$f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}$$$ for $$$x \ge 4$$$.

You have given integers $$$n$$$, $$$f_{1}$$$, $$$f_{2}$$$, $$$f_{3}$$$, and $$$c$$$. Find $$$f_{n} \bmod (10^{9}+7)$$$.

## Input Format
The only line contains five integers $$$n$$$, $$$f_{1}$$$, $$$f_{2}$$$, $$$f_{3}$$$, and $$$c$$$ ($$$4 \le n \le 10^{18}$$$, $$$1 \le f_{1}$$$, $$$f_{2}$$$, $$$f_{3}$$$, $$$c \le 10^{9}$$$).

## Output Format
Print $$$f_{n} \bmod (10^{9} + 7)$$$.

## Examples
```input
5 1 2 5 3
```
```output
72900
```
-----
```input
17 97 41 37 11
```
```output
317451037
```

## Note
In the first example, $$$f_{4} = 90$$$, $$$f_{5} = 72900$$$.

In the second example, $$$f_{17} \approx 2.28 \times 10^{29587}$$$.

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 and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.

After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.

Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).

You have to answer $$$q$$$ independent queries.

Let's see the following example: $$$[1, 3, 4]$$$. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has $$$4$$$ candies, and Bob has $$$4$$$ candies.

Another example is $$$[1, 10, 100]$$$. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes $$$54$$$ candies, and Alice takes $$$46$$$ candies. Now Bob has $$$55$$$ candies, and Alice has $$$56$$$ candies, so she has to discard one candy — and after that, she has $$$55$$$ candies too.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of queries. Then $$$q$$$ queries follow.

The only line of the query contains three integers $$$a, b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^{16}$$$) — the number of candies in the first, second and third piles correspondingly.

## Output Format
Print $$$q$$$ lines. The $$$i$$$-th line should contain the answer for the $$$i$$$-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).

## Examples
```input
4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45
```
```output
4
55
15000000000000000
51
```

Now solve the problem and return the code.