apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
An array $$$b_1, b_2, \ldots, b_n$$$ of positive integers is good if all the sums of two adjacent elements are equal to the same value. More formally, the array is good if there exists a $$$k$$$ such that $$$b_1 + b_2 = b_2 + b_3 = \ldots = b_{n-1} + b_n = k$$$.

Doremy has an array $$$a$$$ of length $$$n$$$. Now Doremy can permute its elements (change their order) however she wants. Determine if she can make the array good.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 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 \le a_i \le 10^5$$$).

There are no constraints on the sum of $$$n$$$ over all test cases.

## Output Format
For each test case, print "Yes" (without quotes), if it is possible to make the array good, and "No" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
5
2
8 9
3
1 1 2
4
1 1 4 5
5
2 3 3 3 3
4
100000 100000 100000 100000
```
```output
Yes
Yes
No
No
Yes
```

## Note
In the first test case, $$$[8,9]$$$ and $$$[9,8]$$$ are good.

In the second test case, $$$[1,2,1]$$$ is good because $$$a_1+a_2=a_2+a_3=3$$$.

In the third test case, it can be shown that no permutation is good.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Qingshan has a string $$$s$$$, while Daniel has a string $$$t$$$. Both strings only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

A string $$$a$$$ of length $$$k$$$ is good if and only if

- $$$a_i \ne a_{i+1}$$$ for all $$$i=1,2,\ldots,k-1$$$.

For example, $$$\texttt{1}$$$, $$$\texttt{101}$$$, $$$\texttt{0101}$$$ are good, while $$$\texttt{11}$$$, $$$\texttt{1001}$$$, $$$\texttt{001100}$$$ are not good.

Qingshan wants to make $$$s$$$ good. To do this, she can do the following operation any number of times (possibly, zero):

- insert $$$t$$$ to any position of $$$s$$$ (getting a new $$$s$$$).

Please tell Qingshan if it is possible to make $$$s$$$ good.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 50$$$) — the length of the strings $$$s$$$ and $$$t$$$, respectively.

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

The third line of each test case contains a string $$$t$$$ of length $$$m$$$.

It is guaranteed that $$$s$$$ and $$$t$$$ only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

## Output Format
For each test case, print "YES" (without quotes), if it is possible to make $$$s$$$ good, and "NO" (without quotes) otherwise.

You can print letters in any case (upper or lower).

## Examples
```input
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10
```
```output
Yes
Yes
No
No
No
```

## Note
In the first test case, $$$s$$$ is good initially, so you can get a good $$$s$$$ by doing zero operations.

In the second test case, you can do the following two operations (the inserted string $$$t$$$ is underlined):

1. $$$\texttt{1}\underline{\texttt{010}}\texttt{11}$$$
2. $$$\texttt{10101}\underline{\texttt{010}}\texttt{1}$$$

and get $$$s = \texttt{101010101}$$$, which is good.

In the third test case, there is no way to make $$$s$$$ good after any number of 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 python3.

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

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

Execution time limit: 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 python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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 python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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 python3.

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
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 python3.

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given 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 python3.

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

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

Execution time limit: 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.