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
Mushroom Filippov cooked himself a meal and while having his lunch, he decided to watch a video on TubeTube. He can not spend more than $$$t$$$ seconds for lunch, so he asks you for help with the selection of video.

The TubeTube feed is a list of $$$n$$$ videos, indexed from $$$1$$$ to $$$n$$$. The $$$i$$$-th video lasts $$$a_i$$$ seconds and has an entertainment value $$$b_i$$$. Initially, the feed is opened on the first video, and Mushroom can skip to the next video in $$$1$$$ second (if the next video exists). Mushroom can skip videos any number of times (including zero).

Help Mushroom choose one video that he can open and watch in $$$t$$$ seconds. If there are several of them, he wants to choose the most entertaining one. Print the index of any appropriate video, or $$$-1$$$ if there is no such.

## Input Format
The first line of the input data contains a single integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of test cases in the test.

The description of the test cases follows.

The first line of a test case contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 50$$$, $$$1 \le t \le 200$$$) — the number of videos in the feed and seconds for lunch, respectively.

The second line of a test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$) — durations of videos.

The third line of a test case contains $$$n$$$ integers $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 100$$$) — entertainment values of videos.

## Output Format
Output $$$q$$$ integers, each of which is the answer to the corresponding test case. As an answer, output the index of the most entertaining video that Mushroom will have time to watch. If there are several answers, you are allowed to output any of them. Output $$$-1$$$, if there is no video he can watch during his lunch break.

## Examples
```input
5
5 9
1 5 7 6 6
3 4 7 1 9
4 4
4 3 3 2
1 2 3 4
5 7
5 5 5 5 5
2 1 3 9 7
4 33
54 71 69 96
42 24 99 1
2 179
55 66
77 88
```
```output
3
2
3
-1
2
```

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
Karina has an array of $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$. She loves multiplying numbers, so she decided that the beauty of a pair of numbers is their product. And the beauty of an array is the maximum beauty of a pair of adjacent elements in the array.

For example, for $$$n = 4$$$, $$$a=[3, 5, 7, 4]$$$, the beauty of the array is $$$\max$$$($$$3 \cdot 5$$$, $$$5 \cdot 7$$$, $$$7 \cdot 4$$$) = $$$\max$$$($$$15$$$, $$$35$$$, $$$28$$$) = $$$35$$$.

Karina wants her array to be as beautiful as possible. In order to achieve her goal, she can remove some elements (possibly zero) from the array. After Karina removes all elements she wants to, the array must contain at least two elements.

Unfortunately, Karina doesn't have enough time to do all her tasks, so she asks you to calculate the maximum beauty of the array that she can get by removing any number of elements (possibly zero).

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

The description of the test cases follows.

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

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

The sum of all values of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Output $$$t$$$ integers, each of which is the answer to the corresponding test case — the maximum beauty of the array that Karina can get.

## Examples
```input
7
4
5 0 2 1
3
-1 1 0
5
2 0 -1 -4 0
6
-8 4 3 7 1 -9
6
0 3 -2 5 -4 -4
2
1000000000 910000000
7
-1 -7 -2 -5 -4 -6 -3
```
```output
10
0
4
72
16
910000000000000000
42
```

## Note
In the first test case of the example, to get the maximum beauty, you need to remove the $$$2$$$-nd element.

In the second and third test cases of the example, there is no need to remove any elements to achieve maximum beauty.

In the fourth test case of the example, you need to leave only the first and last elements.

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: 256.0 MB

# Problem
Tema loves cinnabon rolls — buns with cinnabon and chocolate in the shape of a "snail".

Cinnabon rolls come in different sizes and are square when viewed from above. The most delicious part of a roll is the chocolate, which is poured in a thin layer over the cinnabon roll in the form of a spiral and around the bun, as in the following picture:

Cinnabon rolls of sizes 4, 5, 6

For a cinnabon roll of size $$$n$$$, the length of the outer side of the square is $$$n$$$, and the length of the shortest vertical chocolate segment in the central part is one.

Formally, the bun consists of two dough spirals separated by chocolate. A cinnabon roll of size $$$n + 1$$$ is obtained from a cinnabon roll of size $$$n$$$ by wrapping each of the dough spirals around the cinnabon roll for another layer.

It is important that a cinnabon roll of size $$$n$$$ is defined in a unique way.

Tema is interested in how much chocolate is in his cinnabon roll of size $$$n$$$. Since Tema has long stopped buying small cinnabon rolls, it is guaranteed that $$$n \ge 4$$$.

Answer this non-obvious question by calculating the total length of the chocolate layer.

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

The following $$$t$$$ lines describe the test cases.

Each test case is described by a single integer $$$n$$$ ($$$4 \le n \le 10^9$$$) — the size of the cinnabon roll.

## Output Format
Output $$$t$$$ integers. The $$$i$$$-th of them should be equal to the total length of the chocolate layer in the $$$i$$$-th test case.

## Examples
```input
4
4
5
6
179179179
```
```output
26
37
50
32105178545472401
```

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
A permutation is a sequence $$$n$$$ integers, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. For example, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ are permutations, while $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ are not.

Given a permutation $$$a$$$, we construct an array $$$b$$$, where $$$b_i = (a_1 + a_2 +~\dots~+ a_i) \bmod n$$$.

A permutation of numbers $$$[a_1, a_2, \dots, a_n]$$$ is called a super-permutation if $$$[b_1 + 1, b_2 + 1, \dots, b_n + 1]$$$ is also a permutation of length $$$n$$$.

Grisha became interested whether a super-permutation of length $$$n$$$ exists. Help him solve this non-trivial problem. Output any super-permutation of length $$$n$$$, if it exists. Otherwise, output $$$-1$$$.

## Input Format
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.

Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the desired permutation.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output in a separate line:

- $$$n$$$ integers — a super-permutation of length $$$n$$$, if it exists.
- $$$-1$$$, otherwise.

If there are several suitable permutations, output any of them.

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

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$$$, consisting of lowercase English letters. In one operation, you are allowed to swap any two characters of the string $$$s$$$.

A string $$$s$$$ of length $$$n$$$ is called an anti-palindrome, if $$$s[i] \ne s[n - i + 1]$$$ for every $$$i$$$ ($$$1 \le i \le n$$$). For example, the strings "codeforces", "string" are anti-palindromes, but the strings "abacaba", "abc", "test" are not.

Determine the minimum number of operations required to make the string $$$s$$$ an anti-palindrome, or output $$$-1$$$, if this is not possible.

## Input Format
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.

Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

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

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 minimum number of operations required to make the string $$$s$$$ an anti-palindrome, or $$$-1$$$ if this is not possible.

## Examples
```input
10
10
codeforces
3
abc
10
taarrrataa
10
dcbdbdcccc
4
wwww
12
cabbaccabaac
10
aadaaaaddc
14
aacdaaaacadcdc
6
abccba
12
dcbcaebacccd
```
```output
0
-1
1
1
-1
3
-1
2
2
2
```

## Note
In the first test case, the string "codeforces" is already an anti-palindrome, so the answer is $$$0$$$.

In the second test case, it can be shown that the string "abc" cannot be transformed into an anti-palindrome by performing the allowed operations, so the answer is $$$-1$$$.

In the third test case, it is enough to swap the second and the fifth characters of the string "taarrrataa", and the new string "trararataa" will be an anti-palindrome, so the answer is $$$1$$$.

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
Two friends, Alisa and Yuki, planted a tree with $$$n$$$ vertices in their garden. A tree is an undirected graph without cycles, loops, or multiple edges. Each edge in this tree has a length of $$$k$$$. Initially, vertex $$$1$$$ is the root of the tree.

Alisa and Yuki are growing the tree not just for fun, they want to sell it. The cost of the tree is defined as the maximum distance from the root to a vertex among all vertices of the tree. The distance between two vertices $$$u$$$ and $$$v$$$ is the sum of the lengths of the edges on the path from $$$u$$$ to $$$v$$$.

The girls took a course in gardening, so they know how to modify the tree. Alisa and Yuki can spend $$$c$$$ coins to shift the root of the tree to one of the neighbors of the current root. This operation can be performed any number of times (possibly zero). Note that the structure of the tree is left unchanged; the only change is which vertex is the root.

The friends want to sell the tree with the maximum profit. The profit is defined as the difference between the cost of the tree and the total cost of operations. The profit is cost of the tree minus the total cost of operations.

Help the girls and find the maximum profit they can get by applying operations to the tree any number of times (possibly zero).

## Input Format
The first line of the input contains one 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 integers $$$n$$$, $$$k$$$, $$$c$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k, c \le 10^9$$$) — the number of vertices in the tree, the length of each edge, and the cost of the operation.

The next $$$n - 1$$$ lines of the test case contain pairs of integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — the edges of the graph. These edges form a tree.

The sum of the values 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 profit that Yuki and Alisa can get.

## Examples
```input
4
3 2 3
2 1
3 1
5 4 1
2 1
4 2
5 4
3 4
6 5 3
4 1
6 1
2 6
5 1
3 2
10 6 4
1 3
1 9
9 7
7 6
6 4
9 2
2 8
8 5
5 10
```
```output
2
12
17
32
```

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

# Problem
This is the easy version of the problem. The only difference is that in this version, $$$a_i \le 10^6$$$.

For a given sequence of $$$n$$$ integers $$$a$$$, a triple $$$(i, j, k)$$$ is called magic if:

- $$$1 \le i, j, k \le n$$$.
- $$$i$$$, $$$j$$$, $$$k$$$ are pairwise distinct.
- there exists a positive integer $$$b$$$ such that $$$a_i \cdot b = a_j$$$ and $$$a_j \cdot b = a_k$$$.

Kolya received a sequence of integers $$$a$$$ as a gift and now wants to count the number of magic triples for it. Help him with this task!

Note that there are no constraints on the order of integers $$$i$$$, $$$j$$$ and $$$k$$$.

## Input Format
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 the test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of the sequence.

The second line of the test contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the sequence $$$a$$$.

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 magic triples for the sequence $$$a$$$.

## Examples
```input
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4
```
```output
6
1
3
0
9
16
45
```

## Note
In the first example, there are $$$6$$$ magic triples for the sequence $$$a$$$ — $$$(2, 3, 5)$$$, $$$(2, 5, 3)$$$, $$$(3, 2, 5)$$$, $$$(3, 5, 2)$$$, $$$(5, 2, 3)$$$, $$$(5, 3, 2)$$$.

In the second example, there is a single magic triple for the sequence $$$a$$$ — $$$(2, 1, 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. The only difference is that in this version, $$$a_i \le 10^9$$$.

For a given sequence of $$$n$$$ integers $$$a$$$, a triple $$$(i, j, k)$$$ is called magic if:

- $$$1 \le i, j, k \le n$$$.
- $$$i$$$, $$$j$$$, $$$k$$$ are pairwise distinct.
- there exists a positive integer $$$b$$$ such that $$$a_i \cdot b = a_j$$$ and $$$a_j \cdot b = a_k$$$.

Kolya received a sequence of integers $$$a$$$ as a gift and now wants to count the number of magic triples for it. Help him with this task!

Note that there are no constraints on the order of integers $$$i$$$, $$$j$$$ and $$$k$$$.

## Input Format
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 the test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of the sequence.

The second line of the test contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the sequence $$$a$$$.

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 magic triples for the sequence $$$a$$$.

## Examples
```input
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4
```
```output
6
1
3
0
9
16
45
```

## Note
In the first example, there are $$$6$$$ magic triples for the sequence $$$a$$$ — $$$(2, 3, 5)$$$, $$$(2, 5, 3)$$$, $$$(3, 2, 5)$$$, $$$(3, 5, 2)$$$, $$$(5, 2, 3)$$$, $$$(5, 3, 2)$$$.

In the second example, there is a single magic triple for the sequence $$$a$$$ — $$$(2, 1, 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
There is a group of $$$n$$$ people. Some of them might be liars, who always tell lies. Other people always tell the truth. The $$$i$$$-th person says "There are at least $$$l_i$$$ liars amongst us". Determine if what people are saying is contradictory, or if it is possible. If it is possible, output the number of liars in the group. If there are multiple possible answers, output any one of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

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

The second line of each test case contains $$$n$$$ integers $$$l_i$$$ ($$$0 \leq l_i \leq n$$$) — the number said by the $$$i$$$-th person.

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^4$$$.

## Output Format
For each test case output a single integer. If what people are saying is contradictory, output $$$-1$$$. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.

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

## Note
In the first example, the only possible answer is that the second person is a liar, so the answer is $$$1$$$ liar.

In the second example, it can be proven that we can't choose the liars so that all the requirements are satisfied.

In the third example, everybody tells the truth, so the answer is $$$0$$$ liars.

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 have an array $$$a$$$ of $$$n$$$ non-negative integers. Let's define $$$f(a, x) = [a_1 \bmod x, a_2 \bmod x, \dots, a_n \bmod x]$$$ for some positive integer $$$x$$$. Find the biggest $$$x$$$, such that $$$f(a, x)$$$ is a palindrome.

Here, $$$a \bmod x$$$ is the remainder of the integer division of $$$a$$$ by $$$x$$$.

An array is a palindrome if it reads the same backward as forward. More formally, an array $$$a$$$ of length $$$n$$$ is a palindrome if for every $$$i$$$ ($$$1 \leq i \leq n$$$) $$$a_i = a_{n - i + 1}$$$.

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

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

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

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^5$$$.

## Output Format
For each test case output the biggest $$$x$$$, such that $$$f(a, x)$$$ is a palindrome. If $$$x$$$ can be infinitely large, output $$$0$$$ instead.

## Examples
```input
4
2
1 2
8
3 0 1 2 0 3 2 1
1
0
3
100 1 1000000000
```
```output
1
2
0
999999900
```

## Note
In the first example, $$$f(a, x = 1) = [0, 0]$$$ which is a palindrome.

In the second example, $$$f(a, x = 2) = [1, 0, 1, 0, 0, 1, 0, 1]$$$ which is a palindrome.

It can be proven that in the first two examples, no larger $$$x$$$ satisfies the condition.

In the third example, $$$f(a, x) = [0]$$$ for any $$$x$$$, so we can choose it infinitely large, so the answer is $$$0$$$.

Now solve the problem and return the code.