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
You are given an array $$$a$$$ of length $$$n$$$. You can perform the following operation several (possibly, zero) times:

- Choose $$$i$$$, $$$j$$$, $$$b$$$: Swap the $$$b$$$-th digit in the binary representation of $$$a_i$$$ and $$$a_j$$$.

Find the maximum possible value of $$$\max(a) - \min(a)$$$.

In a binary representation, bits are numbered from right (least significant) to left (most significant). Consider that there are an infinite number of leading zero bits at the beginning of any binary representation.

For example, swap the $$$0$$$-th bit for $$$4=100_2$$$ and $$$3=11_2$$$ will result $$$101_2=5$$$ and $$$10_2=2$$$. Swap the $$$2$$$-nd bit for $$$4=100_2$$$ and $$$3=11_2$$$ will result $$$000_2=0_2=0$$$ and $$$111_2=7$$$.

Here, $$$\max(a)$$$ denotes the maximum element of array $$$a$$$ and $$$\min(a)$$$ denotes the minimum element of array $$$a$$$.

The binary representation of $$$x$$$ is $$$x$$$ written in base $$$2$$$. For example, $$$9$$$ and $$$6$$$ written in base $$$2$$$ are $$$1001$$$ and $$$110$$$, respectively.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 128$$$) — the number of testcases.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 512$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 1024$$$) — the elements of array $$$a$$$.

It's guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$512$$$.

## Output Format
For each testcase, print one integer — the maximum possible value of $$$\max(a) - \min(a)$$$.

## Examples
```input
4
3
1 0 1
4
5 5 5 5
5
1 2 3 4 5
7
20 85 100 41 76 49 36
```
```output
1
0
7
125
```

## Note
In the first example, it can be shown that we do not need to perform any operations — the maximum value of $$$\max(a) - \min(a)$$$ is $$$1 - 0 = 1$$$.

In the second example, no operation can change the array — the maximum value of $$$\max(a) - \min(a)$$$ is $$$5 - 5 = 0$$$.

In the third example, initially $$$a = [1, 2, 3, 4, 5]$$$, we can perform one operation taking $$$i = 2$$$, $$$j = 5$$$, $$$b = 1$$$. The array now becomes $$$a = [1, 0, 3, 4, 7]$$$. It can be shown that any further operations do not lead to a better answer — therefore the answer is $$$\max(a) - \min(a) = 7 - 0 = 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
To destroy humanity, The Monster Association sent $$$n$$$ monsters to Earth's surface. The $$$i$$$-th monster has health $$$h_i$$$ and power $$$p_i$$$.

With his last resort attack, True Spiral Incineration Cannon, Genos can deal $$$k$$$ damage to all monsters alive. In other words, Genos can reduce the health of all monsters by $$$k$$$ (if $$$k > 0$$$) with a single attack.

However, after every attack Genos makes, the monsters advance. With their combined efforts, they reduce Genos' attack damage by the power of the $$$^\dagger$$$weakest monster $$$^\ddagger$$$alive. In other words, the minimum $$$p_i$$$ among all currently living monsters is subtracted from the value of $$$k$$$ after each attack.

$$$^\dagger$$$The Weakest monster is the one with the least power.

$$$^\ddagger$$$A monster is alive if its health is strictly greater than $$$0$$$.

Will Genos be successful in killing all the monsters?

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

The first line of each test case contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^5$$$) — the number of monsters and Genos' initial attack damage. Then two lines follow, each containing $$$n$$$ integers describing the arrays $$$h$$$ and $$$p$$$ ($$$1 \le h_i, p_i \le 10^9$$$).

It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print the answer — "YES" (without quotes) if Genos could kill all monsters and "NO" otherwise.

## Examples
```input
3
6 7
18 5 13 9 10 1
2 7 2 1 2 6
3 4
5 5 5
4 4 4
3 2
2 1 3
1 1 1
```
```output
YES
NO
YES
```

## Note
In the first example, after Genos' first attack, $$$h$$$ and $$$k$$$ will update to:

- $$$h: [11,0,6,2,3,0]$$$
- $$$k: 7-1 = 6$$$

- $$$h: [5,0,0,0,0,0]$$$
- $$$k: 6-2 = 4$$$

- $$$h: [1,0,0,0,0,0]$$$
- $$$k: 4-2 = 2$$$

- $$$h: [0,0,0,0,0,0]$$$

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$$$ of $$$n$$$ integers. You are allowed to perform the following operation on it as many times as you want (0 or more times):

- Choose $$$2$$$ indices $$$i$$$,$$$j$$$ where $$$1 \le i < j \le n$$$ and replace $$$a_k$$$ for all $$$i \leq k \leq j$$$ with $$$|a_i - a_j|$$$

Print the maximum sum of all the elements of the final array that you can obtain in such a way.

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

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

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

It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print the sum of the final array.

## Examples
```input
3
3
1 1 1
2
9 1
3
4 9 5
```
```output
3
16
18
```

## Note
In the first test case, it is not possible to achieve a sum $$$> 3$$$ by using these operations, therefore the maximum sum is $$$3$$$.

In the second test case, it can be shown that the maximum sum achievable is $$$16$$$. By using operation $$$(1,2)$$$ we transform the array from $$$[9,1]$$$ into $$$[8,8]$$$, thus the sum of the final array is $$$16$$$.

In the third test case, it can be shown that it is not possible to achieve a sum $$$> 18$$$ by using these operations, therefore the maximum sum is $$$18$$$.

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
Let's call an ordered pair of nodes $$$(u, v)$$$ in a directed graph unidirectional if $$$u \neq v$$$, there exists a path from $$$u$$$ to $$$v$$$, and there are no paths from $$$v$$$ to $$$u$$$.

A directed graph is called $$$p$$$-reachable if it contains exactly $$$p$$$ ordered pairs of nodes $$$(u, v)$$$ such that $$$u < v$$$ and $$$u$$$ and $$$v$$$ are reachable from each other. Find the minimum number of nodes required to create a $$$p$$$-reachable directed graph.

Also, among all such $$$p$$$-reachable directed graphs with the minimum number of nodes, let $$$G$$$ denote a graph which maximizes the number of unidirectional pairs of nodes. Find this number.

## Input Format
The first and only line contains a single integer $$$p$$$ ($$$0 \le p \le 2 \cdot 10^5$$$) — the number of ordered pairs of nodes.

## Output Format
Print a single line containing two integers — the minimum number of nodes required to create a $$$p$$$-reachable directed graph, and the maximum number of unidirectional pairs of nodes among all such $$$p$$$-reachable directed graphs with the minimum number of nodes.

## Examples
```input
3
```
```output
3 0
```
-----
```input
4
```
```output
5 6
```
-----
```input
0
```
```output
0 0
```

## Note
In the first test case, the minimum number of nodes required to create a $$$3$$$-reachable directed graph is $$$3$$$. Among all $$$3$$$-reachable directed graphs with $$$3$$$ nodes, the following graph $$$G$$$ is one of the graphs with the maximum number of unidirectional pairs of nodes, which is $$$0$$$.

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
You are given an undirected, connected graph of $$$n$$$ nodes and $$$m$$$ edges. All nodes $$$u$$$ of the graph satisfy the following:

- Let $$$S_u$$$ be the set of vertices in the longest simple cycle starting and ending at $$$u$$$.
- Let $$$C_u$$$ be the union of the sets of vertices in any simple cycle starting and ending at $$$u$$$.
- $$$S_u = C_u$$$.

You need to answer $$$q$$$ queries.

For each query, you will be given node $$$a$$$ and node $$$b$$$. Out of all the edges that belong to any simple path from $$$a$$$ to $$$b$$$, count the number of edges such that if you remove that edge, $$$a$$$ and $$$b$$$ are reachable from each other.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min$$$($$$2 \cdot 10^5$$$, $$$(n \cdot (n-1))/2$$$)) — the total number of nodes and edges in the graph, respectively.

The next $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le$$$ $$$u$$$, $$$v$$$ $$$\le n$$$, $$$u \neq v$$$) — describing an edge, implying that nodes $$$u$$$ and $$$v$$$ are connected to each other.

It is guaranteed that there is at most one edge between any pair of vertices in the graph and the given graph is connected.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, each representing a query. Each query contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le$$$ $$$a$$$, $$$b$$$ $$$\le n$$$).

## Output Format
For each query, output a single integer — answer to the query.

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

## Note
The graph in the first sample is :

The first query is $$$(1, 4)$$$. There are $$$5$$$ total edges that belong to any simple path from $$$1$$$ to $$$4$$$. Edges $$$(3, 4), (4, 5), (5, 3)$$$ will be counted in the answer to the query.

The fourth query is $$$(2, 8)$$$. There is only one simple path from $$$2$$$ to $$$8$$$, thus none of the edges will be counted in the answer to the query.

The fifth query is $$$(7, 10)$$$. There are $$$4$$$ total edges that belong to any simple path from $$$7$$$ to $$$10$$$, all of them will be counted in the answer to the query.

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
An array $$$a$$$ is good if for all pairs of adjacent elements, $$$a_i$$$ and $$$a_{i+1}$$$ ($$$1\le i \lt n$$$) are of different parity. Note that an array of size $$$1$$$ is trivially good.

You are given an array of size $$$n$$$.

In one operation you can select any pair of adjacent elements in which both elements are of the same parity, delete them, and insert their product in the same position.

Find the minimum number of operations to form a good array.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{9}$$$).

## Output Format
For each test case print an integer, the minimum number of operations required to form a good array.

## Examples
```input
3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3
```
```output
2
0
3
```

## Note
Consider the first test case. Select the $$$2$$$-nd and the $$$3$$$-rd integers and apply the operation on them. The array changes from $$$[1, \color{red}{7}, \color{red}{11}, 2, 13]$$$ to $$$[1, \color{red}{77}, 2, 13]$$$. Next, select the $$$1$$$-st and the $$$2$$$-nd integers, array changes from $$$[\color{red}{1}, \color{red}{77}, 2, 13]$$$ to $$$[\color{red}{77}, 2, 13]$$$. Thus we require $$$2$$$ operations. It can be proved that this is the minimum number of operations.

In the second test case, the given array is already good. So we require $$$0$$$ operations.

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
A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array). There are $$$n! = n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1$$$ different permutations of length $$$n$$$.

Given a permutation $$$p$$$ of $$$n$$$ numbers, we create an array $$$a$$$ consisting of $$$2n$$$ numbers, which is equal to $$$p$$$ concatenated with its reverse. We then define the beauty of $$$p$$$ as the number of inversions in $$$a$$$.

The number of inversions in the array $$$a$$$ is the number of pairs of indices $$$i$$$, $$$j$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

For example, for permutation $$$p = [1, 2]$$$, $$$a$$$ would be $$$[1, 2, 2, 1]$$$. The inversions in $$$a$$$ are $$$(2, 4)$$$ and $$$(3, 4)$$$ (assuming 1-based indexing). Hence, the beauty of $$$p$$$ is $$$2$$$.

Your task is to find the sum of beauties of all $$$n!$$$ permutations of size $$$n$$$. Print the remainder we get when dividing this value by $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

Each test case has only one line — the integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print one integer — the sum of beauties of all permutations of size $$$n$$$ modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

## Examples
```input
3
1
2
100
```
```output
0
4
389456655
```

## Note
For the first test case of the example, $$$p = [1]$$$ is the only permutation. $$$a = [1, 1]$$$ has $$$0$$$ inversions.

For the second test case of the example, the permutations are $$$[1, 2]$$$ and $$$[2, 1]$$$. Their respective $$$a$$$ arrays are $$$[1, 2, 2, 1]$$$ and $$$[2, 1, 1, 2]$$$, both of which have $$$2$$$ inversions.

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 school has to decide on its team for an international quiz. There are $$$n$$$ students in the school. We can describe the students using an array $$$a$$$ where $$$a_i$$$ is the smartness of the $$$i$$$-th ($$$1 \le i \le n$$$) student.

There are $$$m$$$ topics $$$1, 2, 3, \ldots, m$$$ from which the quiz questions will be formed. The $$$i$$$-th student is considered proficient in a topic $$$T$$$ if $$$(a_i \bmod T) = 0$$$. Otherwise, he is a rookie in that topic.

We say that a team of students is collectively proficient in all the topics if for every topic there is a member of the team proficient in this topic.

Find a team that is collectively proficient in all the topics such that the maximum difference between the smartness of any two students in that team is minimized. Output this difference.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print the answer on a new line. If there is no solution, output $$$-1$$$.

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

## Note
In the first test case, we have participants with smartnesses $$$3$$$ and $$$7$$$, and $$$m = 4$$$. Thus, there is no student with smartness divisible by $$$2$$$. Since $$$2 \leq m$$$, there is no way to choose a team.

In the second test case, we can select the participant with smartness $$$2$$$ to be the only one on the team. This way the team will be collectively proficient in both topics $$$1$$$ and $$$2$$$.

In the third test case, consider the team with participants of smartnesses $$$4, 5, 6, 7$$$. This way the team will be collectively proficient in all topics $$$1, 2, \ldots, 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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a tree of $$$n$$$ nodes, rooted at $$$1$$$. Every node has a value of either $$$0$$$ or $$$1$$$ at time $$$t=0$$$.

At any integer time $$$t>0$$$, the value of a node becomes the bitwise XOR of the values of its children at time $$$t - 1$$$; the values of leaves become $$$0$$$ since they don't have any children.

Let $$$S(t)$$$ denote the sum of values of all nodes at time $$$t$$$.

Let $$$F(A)$$$ denote the sum of $$$S(t)$$$ across all values of $$$t$$$ such that $$$0 \le t \le 10^{100}$$$, where $$$A$$$ is the initial assignment of $$$0$$$s and $$$1$$$s in the tree.

The task is to find the sum of $$$F(A)$$$ for all $$$2^n$$$ initial configurations of $$$0$$$s and $$$1$$$s in the tree. Print the sum modulo $$$10^9+7$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of nodes in the tree.

The next $$$n-1$$$ lines of each test case contain two integers each — $$$u$$$, $$$v$$$ indicating an edge between $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$).

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

## Output Format
Output the sum modulo $$$10^9+7$$$ for each test case.

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

## Note
Let us find $$$F(A)$$$ for the configuration $$$A = [0,1,0,0,1,1]$$$ ($$$A[i]$$$ denotes the value of node $$$i$$$). Initially (at $$$t = 0$$$) our tree is as shown in the picture below. In each node, two values are shown: the number and the value of this node. $$$S(0)$$$ for this configuration is $$$3$$$.

At $$$t = 1$$$ the configuration changes to $$$[1,0,0,0,0,0]$$$. The tree looks as shown below. $$$S(1) = 1$$$.

At $$$t = 2$$$ the configuration changes to $$$[0,0,0,0,0,0]$$$. The tree looks as shown below. $$$S(2) = 0$$$.

For all $$$t>2$$$, the graph remains unchanged, so $$$S(t)=0$$$ for all $$$t > 2$$$. So, for the initial configuration $$$A = [0,1,0,0,1,1]$$$, the value of $$$F(A) = 3 + 1 = 4$$$.

Doing this process for all possible $$$2^{6}$$$ configurations yields us an answer of $$$\textbf{288}$$$.

Now solve the problem and return the code.