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
Theofanis easily gets obsessed with problems before going to sleep and often has nightmares about them. To deal with his obsession he visited his doctor, Dr. Emix.

In his latest nightmare, he has an array $$$a$$$ of size $$$n$$$ and wants to divide it into non-empty subarrays$$$^{\dagger}$$$ such that every element is in exactly one of the subarrays.

For example, the array $$$[1,-3,7,-6,2,5]$$$ can be divided to $$$[1] [-3,7] [-6,2] [5]$$$.

The Cypriot value of such division is equal to $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$$$ where $$$k$$$ is the number of subarrays that we divided the array into and $$$\mathrm{sum}_i$$$ is the sum of the $$$i$$$-th subarray.

The Cypriot value of this division of the array $$$[1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$$$.

Theofanis is wondering what is the maximum Cypriot value of any division of the array.

$$$^{\dagger}$$$ An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

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

Each test case consists of two lines.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^8 \le a_i \le 10^{8}$$$) — the elements of the array.

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 Cypriot value of the array $$$a$$$.

## Examples
```input
4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830
```
```output
32
4
343
830
```

## Note
In the first test case, to get the maximum Cypriot value we divide the array into $$$[1][-3][7][-6][2][5]$$$ which gives us: $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 + 4 \cdot (-6) + 5 \cdot 2 + 6 \cdot 5 = 32$$$

Similarly, in the second test case we divide the array into $$$[2][9,-5,-3]$$$ which gives us $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4$$$.

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
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$ and $$$q$$$, the memory and time limits. You can make hacks only if all versions of the problem are solved.

Theofanis really likes to play with the bits of numbers. He has an array $$$a$$$ of size $$$n$$$ and an integer $$$k$$$. He can make at most $$$k$$$ operations in the array. In each operation, he picks a single element and increases it by $$$1$$$.

He found the maximum bitwise AND that array $$$a$$$ can have after at most $$$k$$$ operations.

Theofanis has put a lot of work into finding this value and was very happy with his result. Unfortunately, Adaś, being the evil person that he is, decided to bully him by repeatedly changing the value of $$$k$$$.

Help Theofanis by calculating the maximum possible bitwise AND for $$$q$$$ different values of $$$k$$$. Note that queries are independent.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$ and $$$n \cdot q \le 10^5$$$) — the size of the array and the number of queries.

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

Next $$$q$$$ lines describe the queries. The $$$i$$$-th line contains one integer $$$k_i$$$ ($$$0 \le k_i \le 10^{18}$$$) — the number of operations that can be done in the $$$i$$$-th query.

## Output Format
For each query, print one integer — the maximum bitwise AND that array $$$a$$$ can have after at most $$$k_i$$$ operations.

## Examples
```input
4 2
1 3 7 5
2
10
```
```output
2
6
```
-----
```input
3 5
4 0 2
9
8
17
1
3
```
```output
5
4
7
0
1
```
-----
```input
1 2
10
5
2318381298321
```
```output
15
2318381298331
```

## Note
In the first test case, in the first query, we add $$$1$$$ in the first and last elements of the array.

Thus, the array becomes $$$[2,3,7,6]$$$ with bitwise AND equal to $$$2$$$.

In the second test case, in the first query, we add $$$1$$$ in the first element, $$$5$$$ in the second, and $$$3$$$ in the third and now all the elements are equal to $$$5$$$.

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

# Problem
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$ and $$$q$$$, the memory and time limits. You can make hacks only if all versions of the problem are solved.

Theofanis really likes to play with the bits of numbers. He has an array $$$a$$$ of size $$$n$$$ and an integer $$$k$$$. He can make at most $$$k$$$ operations in the array. In each operation, he picks a single element and increases it by $$$1$$$.

He found the maximum bitwise AND that array $$$a$$$ can have after at most $$$k$$$ operations.

Theofanis has put a lot of work into finding this value and was very happy with his result. Unfortunately, Adaś, being the evil person that he is, decided to bully him by repeatedly changing the value of $$$k$$$.

Help Theofanis by calculating the maximum possible bitwise AND for $$$q$$$ different values of $$$k$$$. Note that queries are independent.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — the size of the array and the number of queries.

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

Next $$$q$$$ lines describe the queries. The $$$i$$$-th line contains one integer $$$k_i$$$ ($$$0 \le k_i \le 10^{18}$$$) — the number of operations that can be done in the $$$i$$$-th query.

## Output Format
For each query, print one integer — the maximum bitwise AND that array $$$a$$$ can have after at most $$$k_i$$$ operations.

## Examples
```input
4 2
1 3 7 5
2
10
```
```output
2
6
```
-----
```input
3 5
4 0 2
9
8
17
1
3
```
```output
5
4
7
0
1
```
-----
```input
1 2
10
5
2318381298321
```
```output
15
2318381298331
```

## Note
In the first test case, in the first query, we add $$$1$$$ in the first and last elements of the array.

Thus, the array becomes $$$[2,3,7,6]$$$ with bitwise AND equal to $$$2$$$.

In the second test case, in the first query, we add $$$1$$$ in the first element, $$$5$$$ in the second, and $$$3$$$ in the third and now all the elements are equal to $$$5$$$.

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: 7.0 seconds
Memory limit: 256.0 MB

# Problem
Theofanis wants to play video games, however he should also take care of his sister. Since Theofanis is a CS major, he found a way to do both. He will install some cameras in his house in order to make sure his sister is okay.

His house is an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. His sister likes to play at the edges of the graph, so he has to install a camera to at least one endpoint of every edge of the graph. Theofanis wants to find a vertex cover that maximizes the minimum difference between indices of the chosen nodes.

More formally, let $$$a_1, a_2, \ldots, a_k$$$ be a vertex cover of the graph. Let the minimum difference between indices of the chosen nodes be the minimum $$$\lvert a_i - a_j \rvert$$$ (where $$$i \neq j$$$) out of the nodes that you chose. If $$$k = 1$$$ then we assume that the minimum difference between indices of the chosen nodes is $$$n$$$.

Can you find the maximum possible minimum difference between indices of the chosen nodes over all vertex covers?

## 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 two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{5}, 1 \le m \le 2 \cdot 10^{5}$$$) — the number of nodes and the number of edges.

The $$$i$$$-th of the following $$$m$$$ lines in the test case contains two positive integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$), meaning that there exists an edge between them in the graph.

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 $$$2 \cdot 10^{5}$$$.

## Output Format
For each test case, print the maximum minimum difference between indices of the chosen nodes over all vertex covers.

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

## Note
In the first test case, we can install cameras at nodes $$$1$$$, $$$3$$$, and $$$7$$$, so the answer is $$$2$$$.

In the second test case, we can install only one camera at node $$$1$$$, so the answer is $$$3$$$.

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 an array of integers $$$a_1, a_2, \dots, a_n$$$. You can perform the following operation any number of times (possibly zero):

- Choose any element $$$a_i$$$ from the array and change its value to any integer between $$$0$$$ and $$$a_i$$$ (inclusive). More formally, if $$$a_i < 0$$$, replace $$$a_i$$$ with any integer in $$$[a_i, 0]$$$, otherwise replace $$$a_i$$$ with any integer in $$$[0, a_i]$$$.

Let $$$r$$$ be the minimum possible product of all the $$$a_i$$$ after performing the operation any number of times.

Find the minimum number of operations required to make the product equal to $$$r$$$. Also, print one such shortest sequence of operations. If there are multiple answers, you can print any of them.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) - the number of test cases. This is followed by their description.

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

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

## Output Format
For each test case:

- The first line must contain the minimum number of operations $$$k$$$ ($$$0 \leq k \leq n$$$).
- The $$$j$$$-th of the next $$$k$$$ lines must contain two integers $$$i$$$ and $$$x$$$, which represent the $$$j$$$-th operation. That operation consists in replacing $$$a_i$$$ with $$$x$$$.

## Examples
```input
4
1
155
4
2 8 -1 3
4
-1 0 -2 -5
4
-15 -75 -25 -30
```
```output
1
1 0
0
0
1
3 0
```

## Note
In the first test case, we can change the value of the first integer into $$$0$$$ and the product will become $$$0$$$, which is the minimum possible.

In the second test case, initially, the product of integers is equal to $$$2 \cdot 8 \cdot (-1) \cdot 3 = -48$$$ which is the minimum possible, so we should do nothing in this case.

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 string $$$s$$$ of length $$$n$$$. Let's define two operations you can apply on the string:

- remove the first character of the string;
- remove the second character of the string.

Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order.

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

The first line of each test case contains $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$. It is guaranteed that the string only contains lowercase letters of the English alphabet.

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, output a single integer: the number of distinct non-empty strings you can get.

## Examples
```input
5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst
```
```output
5
1
9
50
210
```

## Note
In the first test case, we can get the following strings: $$$a$$$, $$$aa$$$, $$$aaa$$$, $$$aaaa$$$, $$$aaaaa$$$.

In the third test case, for example, the word $$$ba$$$ can be reached in the following way:

- remove the first character of the current string $$$ababa$$$, getting $$$baba$$$;
- remove the second character of the current string $$$baba$$$, getting $$$bba$$$;
- remove the second character of the current string $$$bba$$$, getting $$$ba$$$.

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 permutation $$$p_0, p_1, \ldots, p_{n-1}$$$ of odd integers from $$$1$$$ to $$$2n-1$$$ and a permutation $$$q_0, q_1, \ldots, q_{k-1}$$$ of integers from $$$0$$$ to $$$k-1$$$.

An array $$$a_0, a_1, \ldots, a_{nk-1}$$$ of length $$$nk$$$ is defined as follows:

$$$a_{i \cdot k+j}=p_i \cdot 2^{q_j}$$$ for all $$$0 \le i < n$$$ and all $$$0 \le j < k$$$

For example, if $$$p = [3, 5, 1]$$$ and $$$q = [0, 1]$$$, then $$$a = [3, 6, 5, 10, 1, 2]$$$.

Note that all arrays in the statement are zero-indexed. Note that each element of the array $$$a$$$ is uniquely determined.

Find the number of inversions in the array $$$a$$$. Since this number can be very large, you should find only its remainder modulo $$$998\,244\,353$$$.

An inversion in array $$$a$$$ is a pair $$$(i, j)$$$ ($$$0 \le i < j < nk$$$) such that $$$a_i > a_j$$$.

## 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 two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) — the lengths of arrays $$$p$$$ and $$$q$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$p_0, p_1, \ldots, p_{n-1}$$$ ($$$1 \le p_i \le 2n-1$$$, $$$p_i$$$ is odd) — the array $$$p$$$.

The third line of each test case contains $$$k$$$ distinct integers $$$q_0, q_1, \ldots, q_{k-1}$$$ ($$$0 \le q_i < k$$$) — the array $$$q$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$ and the sum of $$$k$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output one integer: the number of inversions in array $$$a$$$ modulo $$$998\,244\,353$$$.

## Examples
```input
4
3 2
3 5 1
0 1
3 4
1 3 5
3 2 0 1
1 5
1
0 1 2 3 4
8 3
5 1 7 11 15 3 9 13
2 0 1
```
```output
9
25
0
104
```

## Note
In the first test case, array $$$a$$$ is equal to $$$[3, 6, 5, 10, 1, 2]$$$. There are $$$9$$$ inversions in it: $$$(0, 4)$$$, $$$(0, 5)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$. Note that these are pairs $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

In the second test case, array $$$a$$$ is equal to $$$[8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]$$$. There are $$$25$$$ inversions in it.

In the third test case, array $$$a$$$ is equal to $$$[1, 2, 4, 8, 16]$$$. There are no inversions in it.

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 an even integer $$$n$$$ and an integer $$$k$$$. Your task is to construct a matrix of size $$$n \times n$$$ consisting of numbers $$$0$$$ and $$$1$$$ in such a way that the following conditions are true, or report that it is impossible:

- the sum of all the numbers in the matrix is exactly $$$k$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is the same for each $$$i$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is the same for each $$$j$$$.

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

Each test case is described by a single line, which contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 1000$$$, $$$n$$$ is even, $$$0 \leq k \leq n^2$$$).

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

## Output Format
For each test case, output $$$\texttt{Yes}$$$ if it's possible to construct a matrix that satisfies all of the problem's conditions, and $$$\texttt{No}$$$ otherwise.

If it is possible to construct a matrix, the $$$i$$$-th of the next $$$n$$$ lines should contain $$$n$$$ integers representing the elements in the $$$i$$$-th row of the matrix.

## Examples
```input
5
4 0
6 6
6 5
4 2
6 36
```
```output
Yes
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Yes
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
No
No
Yes
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
```

## Note
In the first example, all conditions are satisfied:

- the sum of all the numbers in the matrix is exactly $$$0$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is $$$0$$$ for each $$$i$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is $$$0$$$ for each $$$j$$$.

In the third example, it can be shown that it's impossible to find a matrix satisfying all the problem's conditions.

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 array of integers $$$l_1, l_2, \dots, l_n$$$ and an integer $$$d$$$. Is it possible to construct a tree satisfying the following three conditions?

- The tree contains $$$n + 1$$$ nodes.
- The length of the $$$i$$$-th edge is equal to $$$l_i$$$.
- The (weighted) diameter of the tree is equal to $$$d$$$.

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

The first line of each test case contains two integers $$$n$$$, $$$d$$$ ($$$2 \leq n \leq 2000, 1 \leq d \leq 2000$$$).

The second line of each test case contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$1 \leq l_i \leq d$$$).

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

## Output Format
For each test case, output $$$\texttt{Yes}$$$ if it is possible to construct a tree that satisfies all the conditions, and $$$\texttt{No}$$$ otherwise.

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

## Examples
```input
3
4 10
1 2 3 4
4 7
1 4 3 4
6 18
2 4 3 7 6 7
```
```output
Yes
No
Yes
```

## Note
Below, you are given the illustrations of trees for the first and third test cases. One of the diameters is highlighted by coloring its edges in red.

Now solve the problem and return the code.