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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a_1, a_2, \ldots, a_n$$$. You need to find an array $$$b_1, b_2, \ldots, b_n$$$ consisting of numbers $$$1$$$, $$$2$$$, $$$3$$$ such that exactly two out of the following three conditions are satisfied:

1. There exist indices $$$1 \leq i, j \leq n$$$ such that $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 2$$$.
2. There exist indices $$$1 \leq i, j \leq n$$$ such that $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 3$$$.
3. There exist indices $$$1 \leq i, j \leq n$$$ such that $$$a_i = a_j$$$, $$$b_i = 2$$$, $$$b_j = 3$$$.

If such an array does not exist, you should report it.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 500)$$$ — the number of test cases. Each test case is described as follows.

The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 100)$$$ — the length of the array $$$a$$$.

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

## Output Format
For each test case, print -1 if there is no solution. Otherwise, print $$$b_1, b_2, \ldots, b_n$$$ — an array consisting of numbers $$$1$$$, $$$2$$$, $$$3$$$ that satisfies exactly two out of three conditions. If there are multiple possible answers, you can print any of them.

## Examples
```input
9
6
1 2 3 2 2 3
7
7 7 7 7 7 7 7
4
1 1 2 2
7
1 2 3 4 5 6 7
5
2 3 3 3 2
3
1 2 1
9
1 1 1 7 7 7 9 9 9
1
1
18
93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69
```
```output
1 2 3 1 1 1 
-1
3 2 2 1 
-1
2 1 2 1 3 
-1
1 1 2 2 1 2 2 3 3
-1
3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2
```

## Note
In the first test case, $$$b = [1, 2, 3, 1, 1, 1]$$$ satisfies condition $$$1$$$ because for $$$i = 4$$$, $$$j = 2$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, and $$$b_j = 2$$$. It also satisfies condition $$$2$$$ because for $$$i = 6$$$, $$$j = 3$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, and $$$b_j = 3$$$. However, it does not satisfy condition $$$3$$$. In total, exactly two out of three conditions are satisfied.

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 integer array $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$). In one operation, you can choose an integer $$$x$$$ ($$$0 \le x \le 10^{18}$$$) and replace $$$a_i$$$ with $$$\lfloor \frac{a_i + x}{2} \rfloor$$$ ($$$\lfloor y \rfloor$$$ denotes rounding $$$y$$$ down to the nearest integer) for all $$$i$$$ from $$$1$$$ to $$$n$$$. Pay attention to the fact that all elements of the array are affected on each operation.

Print the smallest number of operations required to make all elements of the array equal.

If the number of operations is less than or equal to $$$n$$$, then print the chosen $$$x$$$ for each operation. If there are multiple answers, print any of them.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print the smallest number of operations required to make all elements of the array equal.

If the number of operations is less than or equal to $$$n$$$, then print the chosen $$$x$$$ for each operation in the next line. If there are multiple answers, print any of them.

## Examples
```input
4
1
10
2
4 6
6
2 1 2 1 2 1
2
0 32
```
```output
0
2
2 5
1
1
6
```

## Note
In the first testcase, all elements are already equal, so $$$0$$$ operations are required. It doesn't matter if you print an empty line afterwards or not.

In the second testcase, you can't make less than $$$2$$$ operations. There are multiple answers, let's consider the answer sequence $$$[2, 5]$$$. After applying an operation with $$$x = 2$$$, the array becomes $$$[\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]$$$. After applying an operation with $$$x = 5$$$ after that, the array becomes $$$[\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]$$$. Both elements are the same, so we are done.

In the last testcase, you can't make less than $$$6$$$ operations. Since $$$6$$$ is greater than $$$n$$$, you don't have to print them. One possible answer sequence is $$$[0, 0, 0, 0, 0, 0]$$$. We are just dividing the second element by $$$2$$$ every time and not changing the first element.

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
Vasya is a sorcerer that fights monsters. Again. There are $$$n$$$ monsters standing in a row, the amount of health points of the $$$i$$$-th monster is $$$a_i$$$.

Vasya is a very powerful sorcerer who knows many overpowered spells. In this fight, he decided to use a chain lightning spell to defeat all the monsters. Let's see how this spell works.

Firstly, Vasya chooses an index $$$i$$$ of some monster ($$$1 \le i \le n$$$) and the initial power of the spell $$$x$$$. Then the spell hits monsters exactly $$$n$$$ times, one hit per monster. The first target of the spell is always the monster $$$i$$$. For every target except for the first one, the chain lightning will choose a random monster who was not hit by the spell and is adjacent to one of the monsters that already was hit. So, each monster will be hit exactly once. The first monster hit by the spell receives $$$x$$$ damage, the second monster receives $$$(x-1)$$$ damage, the third receives $$$(x-2)$$$ damage, and so on.

Vasya wants to show how powerful he is, so he wants to kill all the monsters with a single chain lightning spell. The monster is considered dead if the damage he received is not less than the amount of its health points. On the other hand, Vasya wants to show he doesn't care that much, so he wants to choose the minimum initial power of the spell $$$x$$$ such that it kills all monsters, no matter which monster (among those who can get hit) gets hit on each step.

Of course, Vasya is a sorcerer, but the amount of calculations required to determine the optimal spell setup is way above his possibilities, so you have to help him find the minimum spell power required to kill all the monsters.

Note that Vasya chooses the initial target and the power of the spell, other things should be considered random and Vasya wants to kill all the monsters even in the worst possible scenario.

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

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the amount of health points of the $$$i$$$-th monster.

## Output Format
Print one integer — the minimum spell power required to kill all the monsters if Vasya chooses the first target optimally, and the order of spell hits can be any possible within the given rules.

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

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 a tree consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is equal to $$$a_i$$$.

You can perform the following operation any number of times (possibly zero):

- choose a vertex which has at most $$$1$$$ incident edge and remove this vertex from the tree.

Note that you can delete all vertices.

After all operations are done, you're compressing the tree. The compression process is done as follows. While there is a vertex having exactly $$$2$$$ incident edges in the tree, perform the following operation:

- delete this vertex, connect its neighbors with an edge.

It can be shown that if there are multiple ways to choose a vertex to delete during the compression process, the resulting tree is still the same.

Your task is to calculate the maximum possible sum of numbers written on vertices after applying the aforementioned operation any number of times, and then compressing the tree.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Each of the next $$$n - 1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$v_i$$$ and $$$u_i$$$, the labels of vertices it connects ($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$). These edges form a tree.

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum possible sum of numbers written on vertices after applying the aforementioned operation any number of times, and then compressing the tree.

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

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
Gridlandia has been hit by flooding and now has to reconstruct all of it's cities. Gridlandia can be described by an $$$n \times m$$$ matrix.

Initially, all of its cities are in economic collapse. The government can choose to rebuild certain cities. Additionally, any collapsed city which has at least one vertically neighboring rebuilt city and at least one horizontally neighboring rebuilt city can ask for aid from them and become rebuilt without help from the government. More formally, collapsed city positioned in $$$(i, j)$$$ can become rebuilt if both of the following conditions are satisfied:

- At least one of cities with positions $$$(i + 1, j)$$$ and $$$(i - 1, j)$$$ is rebuilt;
- At least one of cities with positions $$$(i, j + 1)$$$ and $$$(i, j - 1)$$$ is rebuilt.

If the city is located on the border of the matrix and has only one horizontally or vertically neighbouring city, then we consider only that city.

Illustration of two possible ways cities can be rebuilt by adjacent aid. White cells are collapsed cities, yellow cells are initially rebuilt cities (either by the government or adjacent aid), and orange cells are rebuilt cities after adjacent aid.

The government wants to know the minimum number of cities it has to rebuild such that after some time all the cities can be rebuild.

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

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 100$$$) — the sizes of Gridlandia.

## Output Format
For each test case, output a single integer — the minimum number of cities the government needs to rebuild.

## Examples
```input
3
2 2
5 7
3 2
```
```output
2
7
3
```

## Note
In the first test case, it's enough for the government to rebuild cities $$$(1, 2)$$$ and $$$(2, 1)$$$.

In the second test case, it's enough for the government to rebuild cities $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(3, 1)$$$, $$$(3, 6)$$$, $$$(4, 3)$$$, $$$(5, 5)$$$, $$$(5, 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
You are given a tree$$$^{\dagger}$$$. In one zelda-operation you can do follows:

- Choose two vertices of the tree $$$u$$$ and $$$v$$$;
- Compress all the vertices on the path from $$$u$$$ to $$$v$$$ into one vertex. In other words, all the vertices on path from $$$u$$$ to $$$v$$$ will be erased from the tree, a new vertex $$$w$$$ will be created. Then every vertex $$$s$$$ that had an edge to some vertex on the path from $$$u$$$ to $$$v$$$ will have an edge to the vertex $$$w$$$.

Illustration of a zelda-operation performed for vertices $$$1$$$ and $$$5$$$.

Determine the minimum number of zelda-operations required for the tree to have only one vertex.

$$$^{\dagger}$$$A tree is a connected acyclic undirected graph.

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

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

$$$i$$$-th of the next $$$n − 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — the numbers of vertices connected by the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

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

## Output Format
For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.

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

## Note
In the first test case, it's enough to perform one zelda-operation for vertices $$$2$$$ and $$$4$$$.

In the second test case, we can perform the following zelda-operations:

1. $$$u = 2, v = 1$$$. Let the resulting added vertex be labeled as $$$w = 10$$$;
2. $$$u = 4, v = 9$$$. Let the resulting added vertex be labeled as $$$w = 11$$$;
3. $$$u = 8, v = 10$$$. After this operation, the tree consists of a single vertex.

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

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

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

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
In this sad world full of imperfections, ugly segment trees exist.

A segment tree is a tree where each node represents a segment and has its number. A segment tree for an array of $$$n$$$ elements can be built in a recursive manner. Let's say function $$$\operatorname{build}(v,l,r)$$$ builds the segment tree rooted in the node with number $$$v$$$ and it corresponds to the segment $$$[l,r]$$$.

Now let's define $$$\operatorname{build}(v,l,r)$$$:

- If $$$l=r$$$, this node $$$v$$$ is a leaf so we stop adding more edges
- Else, we add the edges $$$(v, 2v)$$$ and $$$(v, 2v+1)$$$. Let $$$m=\lfloor \frac{l+r}{2} \rfloor$$$. Then we call $$$\operatorname{build}(2v,l,m)$$$ and $$$\operatorname{build}(2v+1,m+1,r)$$$.

So, the whole tree is built by calling $$$\operatorname{build}(1,1,n)$$$.

Now Ibti will construct a segment tree for an array with $$$n$$$ elements. He wants to find the sum of $$$\operatorname{lca}^\dagger(S)$$$, where $$$S$$$ is a non-empty subset of leaves. Notice that there are exactly $$$2^n - 1$$$ possible subsets. Since this sum can be very large, output it modulo $$$998\,244\,353$$$.

$$$^\dagger\operatorname{lca}(S)$$$ is the number of the least common ancestor for the nodes that are in $$$S$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^{18}$$$) — the length of the array for which the segment tree is built.

## Output Format
For each test case, output a single integer — the required sum modulo $$$998\,244\,353$$$.

## Examples
```input
5
2
3
4
5
53278
```
```output
6
17
36
69
593324855
```

## Note
In the first test case:

Let's look at all subsets of leaves.

- $$$\operatorname{lca}(\{2\})=2$$$;
- $$$\operatorname{lca}(\{3\})=3$$$;
- $$$\operatorname{lca}(\{2,3\})=1$$$.

Thus, the answer is $$$2+3+1=6$$$.

In the second test case:

Let's look at all subsets of leaves.

- $$$\operatorname{lca}(\{4\})=4$$$;
- $$$\operatorname{lca}(\{5\})=5$$$;
- $$$\operatorname{lca}(\{3\})=3$$$;
- $$$\operatorname{lca}(\{4,5\})=2$$$;
- $$$\operatorname{lca}(\{4,3\})=1$$$;
- $$$\operatorname{lca}(\{5,3\})=1$$$;
- $$$\operatorname{lca}(\{4,5,3\})=1$$$;

Thus, the answer is $$$4+5+3+2+1+1+1=17$$$.

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 a permutation$$$^{\dagger}$$$ $$$p$$$ of length $$$n$$$.

We call index $$$x$$$ good if for all $$$y < x$$$ it holds that $$$p_y < p_x$$$ and for all $$$y > x$$$ it holds that $$$p_y > p_x$$$. We call $$$f(p)$$$ the number of good indices in $$$p$$$.

You can perform the following operation: pick $$$2$$$ distinct indices $$$i$$$ and $$$j$$$ and swap elements $$$p_i$$$ and $$$p_j$$$.

Find the maximum value of $$$f(p)$$$ after applying the aforementioned operation exactly once.

$$$^{\dagger}$$$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).

## Input Format
Each test consists of multiple test cases. The first line of contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contain $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation $$$p$$$.

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

## Output Format
For each test case, output a single integer — the maximum value of $$$f(p)$$$ after performing the operation exactly once.

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

## Note
In the first test case, $$$p = [1,2,3,4,5]$$$ and $$$f(p)=5$$$ which is already maximum possible. But must perform the operation anyway. We can get $$$f(p)=3$$$ by choosing $$$i=1$$$ and $$$j=2$$$ which makes $$$p = [2,1,3,4,5]$$$.

In the second test case, we can transform $$$p$$$ into $$$[1,2,3,4,5]$$$ by choosing $$$i=1$$$ and $$$j=2$$$. Thus $$$f(p)=5$$$.

Now solve the problem and return the code.