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
Right before the UEFA Euro 2020, AmShZ and Safar placed bets on who'd be the champion, AmShZ betting on Italy, and Safar betting on France.

Of course, AmShZ won. Hence, Safar gave him a bracket sequence $$$S$$$. Note that a bracket sequence is a string made of '(' and ')' characters.

AmShZ can perform the following operation any number of times:

- First, he cuts his string $$$S$$$ into three (possibly empty) contiguous substrings $$$A, B$$$ and $$$C$$$. Then, he glues them back by using a '(' and a ')' characters, resulting in a new string $$$S$$$ = $$$A$$$ + "(" + $$$B$$$ + ")" + $$$C$$$.For example, if $$$S$$$ = "))((" and AmShZ cuts it into $$$A$$$ = "", $$$B$$$ = "))", and $$$C$$$ = "((", He will obtain $$$S$$$ = "()))((" as a new string.

After performing some (possibly none) operations, AmShZ gives his string to Keshi and asks him to find the initial string. Of course, Keshi might be able to come up with more than one possible initial string. Keshi is interested in finding the lexicographically smallest possible initial string.

Your task is to help Keshi in achieving his goal.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The only line of input contains a single string $$$S$$$ — the string after the operations $$$(1\le |S|\le 3 \cdot 10^5)$$$.

It is guaranteed that the first character of $$$S$$$ is ')'.

## Output Format
Print the lexicographically smallest possible initial string before operations.

## Examples
```input
)(()(())))
```
```output
)((())))
```

## Note
In the first sample, you can transform ")((())))" into ")(()(())))" by splitting it into ")(", empty string, and "(())))". It can be shown that this is the lexicographically smallest possible initial string

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
After watching the new over-rated series Squid Game, Mashtali and Soroush decided to hold their own Squid Games! Soroush agreed to be the host and will provide money for the winner's prize, and Mashtali became the Front Man!

$$$m$$$ players registered to play in the games to win the great prize, but when Mashtali found out how huge the winner's prize is going to be, he decided to kill eliminate all the players so he could take the money for himself!

Here is how evil Mashtali is going to eliminate players:

There is an unrooted tree with $$$n$$$ vertices. Every player has $$$2$$$ special vertices $$$x_i$$$ and $$$y_i$$$.

In one operation, Mashtali can choose any vertex $$$v$$$ of the tree. Then, for each remaining player $$$i$$$ he finds a vertex $$$w$$$ on the simple path from $$$x_i$$$ to $$$y_i$$$, which is the closest to $$$v$$$. If $$$w\ne x_i$$$ and $$$w\ne y_i$$$, player $$$i$$$ will be eliminated.

Now Mashtali wondered: "What is the minimum number of operations I should perform so that I can remove every player from the game and take the money for myself?"

Since he was only thinking about the money, he couldn't solve the problem by himself and asked for your help!

## Input Format
The first line contains $$$2$$$ integer $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 3 \cdot 10^5)$$$ — the number of vertices of the tree and the number of players.

The second line contains $$$n-1$$$ integers $$$par_2, par_3, \ldots, par_n$$$ $$$(1 \le par_i < i)$$$ — denoting an edge between node $$$i$$$ and $$$par_i$$$.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(1 \le x_i, y_i \le n, x_i \ne y_i)$$$ — the special vertices of the $$$i$$$-th player.

## Output Format
Print the minimum number of operations Mashtali has to perform.

If there is no way for Mashtali to eliminate all the players, print $$$-1$$$.

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

## Note
Explanation for the first sample:

In the first operation, Mashtali can choose vertex $$$1$$$ and eliminate players with colors red and blue. In the second operation, he can choose vertex $$$6$$$ and eliminate the player with orange color.

In the second sample, Mashtali can't eliminate the first player.

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
After many unsuccessful tries, Mashtali decided to copy modify an AtCoder problem. So here is his copied new problem:

There is a tree with $$$n$$$ vertices and some non-empty set of the vertices are pinned to the ground.

Two players play a game against each other on the tree. They alternately perform the following action:

- Remove an edge from the tree, then remove every connected component that has no pinned vertex.The player who cannot move loses(every edge has been deleted already).

You are given the tree, but not the set of the pinned vertices. Your task is to determine, for each $$$k$$$, the winner of the game, if only the vertices $$$1, 2, 3, \ldots, k$$$ are pinned and both players play optimally.

## Input Format
The first line of input contains an integer $$$n$$$ — the number of vertices ($$$1 \le n \le 3 \cdot 10^5$$$).

The $$$i$$$-th of the following $$$n-1$$$ lines contains two integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — the endpoints of the $$$i$$$-th edge. It's guaranteed that these edges form a tree.

## Output Format
Print a string of length $$$n$$$. The $$$i$$$-th character should be '1' if the first player wins the $$$i$$$-th scenario, and '2' otherwise.

## Examples
```input
5
1 2
2 3
2 4
4 5
```
```output
11122
```
-----
```input
5
1 2
2 3
1 4
4 5
```
```output
21122
```
-----
```input
6
1 2
2 4
5 1
6 3
3 2
```
```output
111111
```
-----
```input
7
1 2
3 7
4 6
2 3
2 4
1 5
```
```output
2212222
```

## Note
Below you can see the tree in the first sample :

If $$$k = 1$$$ then the first player can cut the edge $$$(1, 2)$$$.

If $$$k = 2$$$ or $$$k = 3$$$, the first player can cut the edge $$$(2, 4)$$$, after that only the edges $$$(1, 2)$$$ and $$$(2, 3)$$$ remain. After the second players move, there will be a single edge left for the first player to cut. So first player wins.

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 an $$$n \times n$$$ chessboard and $$$k$$$ rooks. Rows of this chessboard are numbered by integers from $$$1$$$ to $$$n$$$ from top to bottom and columns of this chessboard are numbered by integers from $$$1$$$ to $$$n$$$ from left to right. The cell $$$(x, y)$$$ is the cell on the intersection of row $$$x$$$ and collumn $$$y$$$ for $$$1 \leq x \leq n$$$ and $$$1 \leq y \leq n$$$.

The arrangement of rooks on this board is called good, if no rook is beaten by another rook.

A rook beats all the rooks that shares the same row or collumn with it.

The good arrangement of rooks on this board is called not stable, if it is possible to move one rook to the adjacent cell so arrangement becomes not good. Otherwise, the good arrangement is stable. Here, adjacent cells are the cells that share a side.

Such arrangement of $$$3$$$ rooks on the $$$4 \times 4$$$ chessboard is good, but it is not stable: the rook from $$$(1, 1)$$$ can be moved to the adjacent cell $$$(2, 1)$$$ and rooks on cells $$$(2, 1)$$$ and $$$(2, 4)$$$ will beat each other.

Please, find any stable arrangement of $$$k$$$ rooks on the $$$n \times n$$$ chessboard or report that there is no such arrangement.

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

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 40$$$) — the size of the chessboard and the number of rooks.

## Output Format
If there is a stable arrangement of $$$k$$$ rooks on the $$$n \times n$$$ chessboard, output $$$n$$$ lines of symbols . and R. The $$$j$$$-th symbol of the $$$i$$$-th line should be equals R if and only if there is a rook on the cell $$$(i, j)$$$ in your arrangement.

If there are multiple solutions, you may output any of them.

If there is no stable arrangement, output $$$-1$$$.

## Examples
```input
5
3 2
3 3
1 1
5 2
40 33
```
```output
..R
...
R..
-1
R
.....
R....
.....
....R
.....
-1
```

## Note
In the first test case, you should find stable arrangement of $$$2$$$ rooks on the $$$3 \times 3$$$ chessboard. Placing them in cells $$$(3, 1)$$$ and $$$(1, 3)$$$ gives stable arrangement.

In the second test case it can be shown that it is impossbile to place $$$3$$$ rooks on the $$$3 \times 3$$$ chessboard to get stable arrangement.

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
Dasha has $$$10^{100}$$$ coins. Recently, she found a binary string $$$s$$$ of length $$$n$$$ and some operations that allows to change this string (she can do each operation any number of times):

1. Replace substring 00 of $$$s$$$ by 0 and receive $$$a$$$ coins.
2. Replace substring 11 of $$$s$$$ by 1 and receive $$$b$$$ coins.
3. Remove 0 from any position in $$$s$$$ and pay $$$c$$$ coins.

It turned out that while doing this operations Dasha should follow the rule:

- It is forbidden to do two operations with the same parity in a row. Operations are numbered by integers $$$1$$$-$$$3$$$ in the order they are given above.

Please, calculate what is the maximum profit Dasha can get by doing these operations and following this rule.

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

The first line of each test case contains four integers $$$n$$$, $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9$$$).

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case print the answer.

## Examples
```input
3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110
```
```output
3
11
4
```

## Note
In the first test case one of the optimal sequences of operations is 01101 $$$\rightarrow$$$ 0101 $$$\rightarrow$$$ 011 $$$\rightarrow$$$ 01. This sequence of operations consists of operations $$$2$$$, $$$3$$$ and $$$2$$$ in this order. It satisfies all rules and gives profit $$$3$$$. It can be shown that it is impossible to achieve higher profit in this test case, so the answer is $$$3$$$.

In the second test case one of the optimal sequences of operations is 110001 $$$\rightarrow$$$ 11001 $$$\rightarrow$$$ 1001 $$$\rightarrow$$$ 101.

In the third test case one of the optimal sequences of operations is 011110 $$$\rightarrow$$$ 01110 $$$\rightarrow$$$ 1110 $$$\rightarrow$$$ 110 $$$\rightarrow$$$ 11 $$$\rightarrow$$$ 1.

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 the sequence of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$.

The sequence of indices $$$i_1 < i_2 < \ldots < i_k$$$ of length $$$k$$$ denotes the subsequence $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ of length $$$k$$$ of sequence $$$a$$$.

The subsequence $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ of length $$$k$$$ of sequence $$$a$$$ is called increasing subsequence if $$$a_{i_j} < a_{i_{j+1}}$$$ for each $$$1 \leq j < k$$$.

The weight of the increasing subsequence $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ of length $$$k$$$ of sequence $$$a$$$ is the number of $$$1 \leq j \leq k$$$, such that exists index $$$i_k < x \leq n$$$ and $$$a_x > a_{i_j}$$$.

For example, if $$$a = [6, 4, 8, 6, 5]$$$, then the sequence of indices $$$i = [2, 4]$$$ denotes increasing subsequence $$$[4, 6]$$$ of sequence $$$a$$$. The weight of this increasing subsequence is $$$1$$$, because for $$$j = 1$$$ exists $$$x = 5$$$ and $$$a_5 = 5 > a_{i_1} = 4$$$, but for $$$j = 2$$$ such $$$x$$$ doesn't exist.

Find the sum of weights of all increasing subsequences of $$$a$$$ modulo $$$10^9+7$$$.

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

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

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

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

## Output Format
For each test case, print the sum of weights of all increasing subsequences $$$a$$$ modulo $$$10^9+7$$$.

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

## Note
In the first test case the following increasing subsequences of $$$a$$$ have not zero weight:

- The weight of $$$[a_1] = [6]$$$ is $$$1$$$.
- The weight of $$$[a_2] = [4]$$$ is $$$1$$$.
- The weight of $$$[a_2, a_3] = [4, 8]$$$ is $$$1$$$.
- The weight of $$$[a_2, a_4] = [4, 6]$$$ is $$$1$$$.

In the second test case there are $$$7$$$ increasing subsequences of $$$a$$$ with not zero weight: $$$3$$$ with weight $$$1$$$, $$$3$$$ with weight $$$2$$$ and $$$1$$$ with weight $$$3$$$. The sum of weights is $$$12$$$.

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
Madoka's father just reached $$$1$$$ million subscribers on Mathub! So the website decided to send him a personalized award — The Mathhub's Bit Button!

The Bit Button is a rectangular table with $$$n$$$ rows and $$$m$$$ columns with $$$0$$$ or $$$1$$$ in each cell. After exploring the table Madoka found out that:

- A subrectangle $$$A$$$ is contained in a subrectangle $$$B$$$ if there's no cell contained in $$$A$$$ but not contained in $$$B$$$.
- Two subrectangles intersect if there is a cell contained in both of them.
- A subrectangle is called black if there's no cell with value $$$0$$$ inside it.
- A subrectangle is called nice if it's black and it's not contained in another black subrectangle.
- The table is called elegant if there are no two nice intersecting subrectangles.

For example, in the first illustration the red subrectangle is nice, but in the second one it's not, because it's contained in the purple subrectangle.

Help Madoka to determine whether the table is elegant.

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

The first line of each test case contains two positive integers $$$n, m$$$ ($$$1 \le n, m \le 100$$$).

The next $$$n$$$ lines contain strings of length $$$m$$$ consisting of zeros and ones — the description of the table.

It is guaranteed that the sum of the values of $$$n$$$ and the sum of the values of $$$m$$$ for all test cases do not exceed $$$777$$$.

## Output Format
For each test case print "YES" if its table is elegant or print "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

## Examples
```input
5
3 3
100
011
011
3 3
110
111
110
1 5
01111
4 5
11111
01010
01000
01000
3 2
11
00
11
```
```output
YES
NO
YES
NO
YES
```

## Note
In the second test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.

In the fourth test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.

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
There are $$$n$$$ logs, the $$$i$$$-th log has a length of $$$a_i$$$ meters. Since chopping logs is tiring work, errorgorn and maomao90 have decided to play a game.

errorgorn and maomao90 will take turns chopping the logs with errorgorn chopping first. On his turn, the player will pick a log and chop it into $$$2$$$ pieces. If the length of the chosen log is $$$x$$$, and the lengths of the resulting pieces are $$$y$$$ and $$$z$$$, then $$$y$$$ and $$$z$$$ have to be positive integers, and $$$x=y+z$$$ must hold. For example, you can chop a log of length $$$3$$$ into logs of lengths $$$2$$$ and $$$1$$$, but not into logs of lengths $$$3$$$ and $$$0$$$, $$$2$$$ and $$$2$$$, or $$$1.5$$$ and $$$1.5$$$.

The player who is unable to make a chop will be the loser. Assuming that both errorgorn and maomao90 play optimally, who will be the winner?

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$)  — the number of logs.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 50$$$)  — the lengths of the logs.

Note that there is no bound on the sum of $$$n$$$ over all test cases.

## Output Format
For each test case, print "errorgorn" if errorgorn wins or "maomao90" if maomao90 wins. (Output without quotes).

## Examples
```input
2
4
2 4 2 1
1
1
```
```output
errorgorn
maomao90
```

## Note
In the first test case, errorgorn will be the winner. An optimal move is to chop the log of length $$$4$$$ into $$$2$$$ logs of length $$$2$$$. After this there will only be $$$4$$$ logs of length $$$2$$$ and $$$1$$$ log of length $$$1$$$.

After this, the only move any player can do is to chop any log of length $$$2$$$ into $$$2$$$ logs of length $$$1$$$. After $$$4$$$ moves, it will be maomao90's turn and he will not be able to make a move. Therefore errorgorn will be the winner.

In the second test case, errorgorn will not be able to make a move on his first turn and will immediately lose, making maomao90 the winner.

Now solve the problem and return the code.