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: 8.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers.

The numbness of a subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ (for arbitrary $$$l \leq r$$$) is defined as $$$$$$\max(a_l, a_{l+1}, \ldots, a_r) \oplus (a_l \oplus a_{l+1} \oplus \ldots \oplus a_r),$$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation.

Find the maximum numbness over all subarrays.

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

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

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

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

## Output Format
For each test case, print one integer — the maximum numbness over all subarrays of the given array.

## Examples
```input
2
5
1 2 3 4 5
3
10 47 52
```
```output
7
47
```

## Note
For the first test case, for the subarray $$$[3, 4, 5]$$$, its maximum value is $$$5$$$. Hence, its numbness is $$$3 \oplus 4 \oplus 5 \oplus 5$$$ = $$$7$$$. This is the maximum possible numbness in this array.

In the second test case the subarray $$$[47, 52]$$$ provides the maximum numbness.

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
This is an easy version of the problem. In this version, all cards have the same color.

Alice has $$$n$$$ cards, each card is white, and the cards are stacked in a deck. Alice deals the cards to herself and to Bob, dealing at once several cards from the top of the deck in the following order: one card to herself, two cards to Bob, three cards to Bob, four cards to herself, five cards to herself, six cards to Bob, seven cards to Bob, eight cards to herself, and so on. In other words, on the $$$i$$$-th step, Alice deals $$$i$$$ top cards from the deck to one of the players; on the first step, she deals the cards to herself and then alternates the players every two steps. When there aren't enough cards at some step, Alice deals all the remaining cards to the current player, and the process stops.

First Alice's steps in a deck of many cards.

How many cards will Alice and Bob have at the end?

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of cards.

## Output Format
For each test case print two integers — the number of cards in the end for each player — in this order: cards Alice has, cards Bob has.

## Examples
```input
5
10
6
17
8
1000000
```
```output
5 5
1 5
10 7
3 5
500202 499798
```

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
There is an array $$$a$$$ consisting of non-negative integers. You can choose an integer $$$x$$$ and denote $$$b_i=a_i \oplus x$$$ for all $$$1 \le i \le n$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. Is it possible to choose such a number $$$x$$$ that the value of the expression $$$b_1 \oplus b_2 \oplus \ldots \oplus b_n$$$ equals $$$0$$$?

It can be shown that if a valid number $$$x$$$ exists, then there also exists $$$x$$$ such that ($$$0 \le x < 2^8$$$).

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the length of the array $$$a$$$.

The second line of the test case contains $$$n$$$ integers — array $$$a$$$ ($$$0 \le a_i < 2^8$$$).

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

## Output Format
For each set test case, print the integer $$$x$$$ ($$$0 \le x < 2^8$$$) if it exists, or $$$-1$$$ otherwise.

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

## Note
In the first test case, after applying the operation with the number $$$6$$$ the array $$$b$$$ becomes $$$[7, 4, 3]$$$, $$$7 \oplus 4 \oplus 3 = 0$$$.

There are other answers in the third test case, such as the number $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$. You can apply this operation to the string exactly once: choose index $$$i$$$ and move character $$$s_i$$$ to the beginning of the string (removing it at the old position). For example, if you apply the operation with index $$$i=4$$$ to the string "abaacd" with numbering from $$$1$$$, you get the string "aabacd". What is the lexicographically minimal$$$^{\dagger}$$$ string you can obtain by this operation?

$$$^{\dagger}$$$A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length if and only if the following holds:

- 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
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 a single integer $$$n$$$ ($$$1 \le n \le 10 ^ 5$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

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

## Output Format
For each test case, on a separate line print the lexicographically smallest string that can be obtained after applying the operation to the original string exactly once.

## Examples
```input
4
3
cba
4
acac
5
abbcb
4
aaba
```
```output
acb
aacc
abbcb
aaab
```

## Note
In the first test case, you need to move the last character to the beginning.

In the second case, you need to move the second letter "a".

In the third set you need to apply the operation with $$$i=1$$$, then the string will not change.

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 a tree (a connected graph without cycles) with $$$n$$$ vertices.

Consider a fixed integer $$$k$$$. Then, the graph $$$G_k$$$ is an undirected graph with $$$n$$$ vertices, where an edge between vertices $$$u$$$ and $$$v$$$ exists if and only if the distance between vertices $$$u$$$ and $$$v$$$ in the given tree is at least $$$k$$$.

For each $$$k$$$ from $$$1$$$ to $$$n$$$, print the number of connected components in the graph $$$G_k$$$.

## Input Format
The first line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the graph.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$ in the tree. It is guaranteed that these edges form a valid tree.

## Output Format
Output $$$n$$$ integers: the number of connected components in the graph $$$G_k$$$ for each $$$k$$$ from $$$1$$$ to $$$n$$$.

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

## Note
In the first example: If $$$k=1$$$, the graph has an edge between each pair of vertices, so it has one component. If $$$k=4$$$, the graph has only edges $$$4 \leftrightarrow 6$$$ and $$$5 \leftrightarrow 6$$$, so the graph has $$$4$$$ components.

In the second example: when $$$k=1$$$ or $$$k=2$$$ the graph has one component. When $$$k=3$$$ the graph $$$G_k$$$ splits into $$$3$$$ components: one component has vertices $$$1$$$, $$$4$$$ and $$$5$$$, and two more components contain one vertex each. When $$$k=4$$$ or $$$k=5$$$ each vertex is a separate component.

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 a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the $$$\mathrm{MAD}$$$ (maximum double) parameter of the tree as the maximum integer that occurs in the vertices of the tree at least $$$2$$$ times. If no number occurs in the tree more than once, then we assume $$$\mathrm{MAD}=0$$$.

Note that if you remove an edge from the tree, it splits into two trees. Let's compute the $$$\mathrm{MAD}$$$ parameters of the two trees and take the maximum of the two values. Let the result be the value of the deleted edge.

For each edge, find its value. Note that we don't actually delete any edges from the tree, the values are to be found independently.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.

The last line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers in the vertices.

## Output Format
For each edge in the input order, print one number — the maximum of the $$$\mathrm{MAD}$$$ parameters of the two trees obtained after removing the given edge from the initial tree.

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

## Note
In the first example, after removing edge $$$(1, 2)$$$ no number repeats $$$2$$$ times in any of the resulting subtrees, so the answer is $$$\max(0, 0)=0$$$.

After removing edge $$$(2, 3)$$$, in the bigger subtree, $$$1$$$ is repeated twice, and $$$2$$$ is repeated twice, so the $$$\mathrm{MAD}$$$ of this tree is $$$2$$$.

After removing edge $$$(2, 4)$$$, in the bigger subtree, only the number $$$1$$$ is repeated, and in the second subtree, only one number appears, so the answer is $$$1$$$.

In the second example, if edge $$$1 \leftrightarrow 4$$$ is not removed, then one of the subtrees will have two $$$1$$$, so the answer — $$$1$$$. And if edge $$$1 \leftrightarrow 4$$$ is deleted, both subtrees have no repeating values, so the answer 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
This is the easy version of the problem. It differs from the hard one only in constraints on $$$n$$$. You can make hacks only if you lock both versions.

Let $$$a_1, a_2, \ldots, a_n$$$ be an array of non-negative integers. Let $$$F(a_1, a_2, \ldots, a_n)$$$ be the sorted in the non-decreasing order array of $$$n - 1$$$ smallest numbers of the form $$$a_i + a_j$$$, where $$$1 \le i < j \le n$$$. In other words, $$$F(a_1, a_2, \ldots, a_n)$$$ is the sorted in the non-decreasing order array of $$$n - 1$$$ smallest sums of all possible pairs of elements of the array $$$a_1, a_2, \ldots, a_n$$$. For example, $$$F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$$$.

You are given an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Determine the single element of the array $$$\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$$$. Since the answer can be quite large, output it modulo $$$10^9+7$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3000$$$) — the initial length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array elements.

## Output Format
Output a single number — the answer modulo $$$10^9 + 7$$$.

## Examples
```input
5
1 2 4 5 6
```
```output
34
```
-----
```input
9
1 1 1 7 7 7 9 9 9
```
```output
256
```
-----
```input
7
1 7 9 2 0 0 9
```
```output
20
```
-----
```input
3
1000000000 1000000000 777
```
```output
1540
```

## Note
In the first test, the array is transformed as follows: $$$[1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34]$$$. The only element of the final array is $$$34$$$.

In the second test, $$$F(a_1, a_2, \ldots, a_n)$$$ is $$$[2, 2, 2, 8, 8, 8, 8, 8]$$$. This array is made up of $$$3$$$ numbers of the form $$$1 + 1$$$ and $$$5$$$ numbers of the form $$$1 + 7$$$.

In the fourth test, the array is transformed as follows: $$$[10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554]$$$. $$$2 \cdot 10^9 + 1554$$$ modulo $$$10^9+7$$$ equals $$$1540$$$.

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
This is the hard version of the problem. It differs from the easy one only in constraints on $$$n$$$. You can make hacks only if you lock both versions.

Let $$$a_1, a_2, \ldots, a_n$$$ be an array of non-negative integers. Let $$$F(a_1, a_2, \ldots, a_n)$$$ be the sorted in the non-decreasing order array of $$$n - 1$$$ smallest numbers of the form $$$a_i + a_j$$$, where $$$1 \le i < j \le n$$$. In other words, $$$F(a_1, a_2, \ldots, a_n)$$$ is the sorted in the non-decreasing order array of $$$n - 1$$$ smallest sums of all possible pairs of elements of the array $$$a_1, a_2, \ldots, a_n$$$. For example, $$$F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$$$.

You are given an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Determine the single element of the array $$$\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$$$. Since the answer can be quite large, output it modulo $$$10^9+7$$$.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array elements.

## Output Format
Output a single number — the answer modulo $$$10^9 + 7$$$.

## Examples
```input
5
1 2 4 5 6
```
```output
34
```
-----
```input
9
1 1 1 7 7 7 9 9 9
```
```output
256
```
-----
```input
7
1 7 9 2 0 0 9
```
```output
20
```
-----
```input
3
1000000000 1000000000 777
```
```output
1540
```

## Note
In the first test, the array is transformed as follows: $$$[1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34]$$$. The only element of the final array is $$$34$$$.

In the second test, $$$F(a_1, a_2, \ldots, a_n)$$$ is $$$[2, 2, 2, 8, 8, 8, 8, 8]$$$. This array is made up of $$$3$$$ numbers of the form $$$1 + 1$$$ and $$$5$$$ numbers of the form $$$1 + 7$$$.

In the fourth test, the array is transformed as follows: $$$[10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554]$$$. $$$2 \cdot 10^9 + 1554$$$ modulo $$$10^9+7$$$ equals $$$1540$$$.

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
Conveyor matrix $$$m_n$$$ is matrix of size $$$n \times n$$$, where $$$n$$$ is an even number. The matrix consists of concentric ribbons moving clockwise.

In other words, the conveyor matrix for $$$n = 2$$$ is simply a matrix $$$2 \times 2$$$, whose cells form a cycle of length $$$4$$$ clockwise. For any natural $$$k \ge 2$$$, the matrix $$$m_{2k}$$$ is obtained by adding to the matrix $$$m_{2k - 2}$$$ an outer layer forming a clockwise cycle.

The conveyor matrix $$$8 \times 8$$$.

You are standing in a cell with coordinates $$$x_1, y_1$$$ and you want to get into a cell with coordinates $$$x_2, y_2$$$. A cell has coordinates $$$x, y$$$ if it is located at the intersection of the $$$x$$$th row and the $$$y$$$th column.

Standing on some cell, every second you will move to the cell next in the direction of movement of the tape on which you are. You can also move to a neighboring cell by spending one unit of energy. Movements happen instantly and you can make an unlimited number of them at any time.

Your task is to find the minimum amount of energy that will have to be spent to get from the cell with coordinates $$$x_1, y_1$$$ to the cell with coordinates $$$x_2, y_2$$$.

For example, $$$n=8$$$ initially you are in a cell with coordinates $$$1,3$$$ and you want to get into a cell with coordinates $$$6, 4$$$. You can immediately make $$$2$$$ movements, once you are in a cell with coordinates $$$3, 3$$$, and then after $$$8$$$ seconds you will be in the right cell.

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

The descriptions of the test cases follow.

The description of each test case consists of one string containing five integers $$$n$$$, $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ ($$$1 \le x_1, y_1, x_2, y_2 \le n \le 10^9$$$) — matrix size and the coordinates of the start and end cells. It is guaranteed that the number $$$n$$$ is even.

## Output Format
For each test case, print one integer in a separate line — the minimum amount of energy that will have to be spent to get from the cell with coordinates $$$x_1, y_1$$$ to the cell with coordinates $$$x_2, y_2$$$.

## Examples
```input
5
2 1 1 2 2
4 1 4 3 3
8 1 3 4 6
100 10 20 50 100
1000000000 123456789 987654321 998244353 500000004
```
```output
0
1
2
9
10590032
```

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
The girl Umka loves to travel and participate in math olympiads. One day she was flying by plane to the next olympiad and out of boredom explored a huge checkered sheet of paper.

Denote the $$$n$$$-th Fibonacci number as $$$F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$$$

A checkered rectangle with a height of $$$F_n$$$ and a width of $$$F_{n+1}$$$ is called a Fibonacci rectangle of order $$$n$$$.

Umka has a Fibonacci rectangle of order $$$n$$$. Someone colored a cell in it at the intersection of the row $$$x$$$ and the column $$$y$$$.

It is necessary to cut this rectangle exactly into $$$n+1$$$ squares in such way that

- the painted cell was in a square with a side of $$$1$$$;
- there was at most one pair of squares with equal sides;
- the side of each square was equal to a Fibonacci number.

Will Umka be able to cut this rectangle in that way?

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

For each test case the integers $$$n$$$, $$$x$$$, $$$y$$$ are given ($$$1 \le n \le 44$$$, $$$1 \le x \le F_n$$$, $$$1 \le y \le F_{n+1}$$$) — the order of the Fibonacci rectangle and the coordinates of the colored cell.

## Output Format
For each test case, print "YES" if the answer is positive, and "NO" otherwise.

You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer).

## Examples
```input
12
1 1 1
2 1 2
3 1 4
3 3 2
4 4 6
4 3 3
5 6 5
5 4 12
5 2 12
4 2 1
1 1 2
44 758465880 1277583853
```
```output
YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
```

## Note
The first, third and fourth test cases.

Now solve the problem and return the code.