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
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 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
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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
This is the easy version of the problem. The only difference is maximum value of $$$a_i$$$.

Once in Kostomuksha Divan found an array $$$a$$$ consisting of positive integers. Now he wants to reorder the elements of $$$a$$$ to maximize the value of the following function: $$$$$$\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),$$$$$$ where $$$\operatorname{gcd}(x_1, x_2, \ldots, x_k)$$$ denotes the greatest common divisor of integers $$$x_1, x_2, \ldots, x_k$$$, and $$$\operatorname{gcd}(x) = x$$$ for any integer $$$x$$$.

Reordering elements of an array means changing the order of elements in the array arbitrary, or leaving the initial order.

Of course, Divan can solve this problem. However, he found it interesting, so he decided to share it with you.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_{1}, \, a_{2}, \, \dots, \, a_{n}$$$ ($$$1 \le a_{i} \le 5 \cdot 10^6$$$) — the array $$$a$$$.

## Output Format
Output the maximum value of the function that you can get by reordering elements of the array $$$a$$$.

## Examples
```input
6
2 3 1 2 6 2
```
```output
14
```
-----
```input
10
5 7 10 3 1 10 100 3 42 54
```
```output
131
```

## Note
In the first example, it's optimal to rearrange the elements of the given array in the following order: $$$[6, \, 2, \, 2, \, 2, \, 3, \, 1]$$$:

$$$$$$\operatorname{gcd}(a_1) + \operatorname{gcd}(a_1, \, a_2) + \operatorname{gcd}(a_1, \, a_2, \, a_3) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5, \, a_6) = 6 + 2 + 2 + 2 + 1 + 1 = 14.$$$$$$ It can be shown that it is impossible to get a better answer.

In the second example, it's optimal to rearrange the elements of a given array in the following order: $$$[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
This is the hard version of the problem. The only difference is maximum value of $$$a_i$$$.

Once in Kostomuksha Divan found an array $$$a$$$ consisting of positive integers. Now he wants to reorder the elements of $$$a$$$ to maximize the value of the following function: $$$$$$\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),$$$$$$ where $$$\operatorname{gcd}(x_1, x_2, \ldots, x_k)$$$ denotes the greatest common divisor of integers $$$x_1, x_2, \ldots, x_k$$$, and $$$\operatorname{gcd}(x) = x$$$ for any integer $$$x$$$.

Reordering elements of an array means changing the order of elements in the array arbitrary, or leaving the initial order.

Of course, Divan can solve this problem. However, he found it interesting, so he decided to share it with you.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_{1}, \, a_{2}, \, \dots, \, a_{n}$$$ ($$$1 \le a_{i} \le 2 \cdot 10^7$$$) — the array $$$a$$$.

## Output Format
Output the maximum value of the function that you can get by reordering elements of the array $$$a$$$.

## Examples
```input
6
2 3 1 2 6 2
```
```output
14
```
-----
```input
10
5 7 10 3 1 10 100 3 42 54
```
```output
131
```

## Note
In the first example, it's optimal to rearrange the elements of the given array in the following order: $$$[6, \, 2, \, 2, \, 2, \, 3, \, 1]$$$:

$$$$$$\operatorname{gcd}(a_1) + \operatorname{gcd}(a_1, \, a_2) + \operatorname{gcd}(a_1, \, a_2, \, a_3) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5, \, a_6) = 6 + 2 + 2 + 2 + 1 + 1 = 14.$$$$$$ It can be shown that it is impossible to get a better answer.

In the second example, it's optimal to rearrange the elements of a given array in the following order: $$$[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$$$.

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 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 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
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 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 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 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
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.