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: 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 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
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 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: 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 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: 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 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
John is a lead programmer on a destroyer belonging to the space navy of the Confederacy of Independent Operating Systems. One of his tasks is checking if the electronic brains of robots were damaged during battles.

A standard test is to order the robots to form one or several lines, in each line the robots should stand one after another. After that, each robot reports the number of robots standing in front of it in its line.

An example of robots' arrangement (the front of the lines is on the left). The robots report the numbers above.

The $$$i$$$-th robot reported number $$$l_i$$$. Unfortunately, John does not know which line each robot stands in, and can't check the reported numbers. Please determine if it is possible to form the lines in such a way that all reported numbers are correct, or not.

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

The first line in each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of robots.

The second line in each test case contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$0 \leq l_i < 100$$$), $$$l_i$$$ is equal to the number of robots in front of the $$$i$$$-th robot in its line.

The sum of $$$n$$$ over all test cases won't exceed $$$200$$$.

## Output Format
For each test case, output "YES", if there exists a robot arrangement consistent with robots' reports. Otherwise, output "NO".

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
6
0 1 2 0 1 0
9
0 0 0 0 1 1 1 2 2
3
0 0 2
1
99
5
0 1 2 3 4
```
```output
YES
YES
NO
NO
YES
```

## Note
Example arrangement consistent with robot statements from the first example test case:

Example arrangement consistent with robot statements from the second example is shown in the statement.

In the third test case, the third robot claims that there are two machines in front of it. In such a case, the robot directly in front of it would have one machine in front. No robot claims that, so there is no valid arrangement.

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
Rishi is developing games in the 2D metaverse and wants to offer game bundles to his customers. Each game has an associated enjoyment value. A game bundle consists of a subset of games whose total enjoyment value adds up to $$$60$$$.

Your task is to choose $$$k$$$ games, where $$$1 \leq k \leq 60$$$, along with their respective enjoyment values $$$a_1, a_2, \dots, a_k$$$, in such a way that exactly $$$m$$$ distinct game bundles can be formed.

## Input Format
The input is a single integer $$$m$$$ ($$$1 \le m \le 10^{10}$$$) — the desired number of game bundles.

## Output Format
The first line should contain an integer $$$k$$$ ($$$1 \le k \le 60$$$) — the number of games.

The second line should contain $$$k$$$ integers, $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_1, a_2, \dots, a_k \le 60$$$) — the enjoyment values of the $$$k$$$ games.

## Examples
```input
4
```
```output
4
20 20 20 20
```
-----
```input
722
```
```output
15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
```
-----
```input
1
```
```output
1
60
```

## Note
In the first sample, any subset of size $$$3$$$ is a game bundle. There are $$$4$$$ such subsets.

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

# Problem
A prime number is a positive integer that has exactly two different positive divisors: $$$1$$$ and the integer itself. For example, $$$2$$$, $$$3$$$, $$$13$$$ and $$$101$$$ are prime numbers; $$$1$$$, $$$4$$$, $$$6$$$ and $$$42$$$ are not.

You are given a sequence of digits from $$$1$$$ to $$$9$$$, in which every digit from $$$1$$$ to $$$9$$$ appears exactly once.

You are allowed to do the following operation several (maybe zero) times: choose any digit from the sequence and delete it. However, you cannot perform this operation if the sequence consists of only two digits.

Your goal is to obtain a sequence which represents a prime number. Note that you cannot reorder the digits in the sequence.

Print the resulting sequence, or report that it is impossible to perform the operations so that the resulting sequence is a prime number.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each test case consists of one line containing a string of $$$9$$$ digits (without any characters between them). Each digit from $$$1$$$ to $$$9$$$ appears in this string exactly once.

## Output Format
For each test case, print the answer on a separate line as follows:

- if it is impossible to perform the described operations, print $$$-1$$$;
- otherwise, print any sequence that represents a prime number, which can be obtained from the given string performing several (maybe zero) operations described in the statement. If there are multiple such sequences, you can print any one of them.

## Examples
```input
4
123456789
987654321
243567918
576318429
```
```output
167
53
3571
57638429
```

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 array $$$a$$$ of length $$$n$$$, consisting of positive integers.

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

- choose three integers $$$l$$$, $$$r$$$ and $$$x$$$ such that $$$1 \le l \le r \le n$$$, and multiply every $$$a_i$$$ such that $$$l \le i \le r$$$ by $$$x$$$.

Note that you can choose any integer as $$$x$$$, it doesn't have to be positive.

You have to calculate the minimum number of operations to make the array $$$a$$$ sorted in strictly ascending order (i. e. the condition $$$a_1 < a_2 < \dots < a_n$$$ must be satisfied).

## 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 one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)  — the length of the array $$$a$$$.

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

Additional constraint on the input: 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 minimum number of operations required to make $$$a$$$ sorted in strictly ascending order.

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

## Note
In the first test case, we can perform the operations as follows:

- $$$l = 2$$$, $$$r = 4$$$, $$$x = 3$$$;
- $$$l = 4$$$, $$$r = 4$$$, $$$x = 2$$$;
- $$$l = 5$$$, $$$r = 5$$$, $$$x = 10$$$.

In the second test case, we can perform one operation as follows:

- $$$l = 1$$$, $$$r = 4$$$, $$$x = -2$$$;
- $$$l = 6$$$, $$$r = 6$$$, $$$x = 1337$$$.

In the third test case, the array $$$a$$$ is already sorted.

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
Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

- After the cutting each ribbon piece should have length a, b or c.
- After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

## Input Format
The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

## Output Format
Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

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

## Note
In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3.

In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 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 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 have two positive integers w and h. Your task is to count the number of rhombi which have the following properties:

- Have positive area.
- With vertices at integer points.
- All vertices of the rhombi are located inside or on the border of the rectangle with vertices at points (0, 0), (w, 0), (w, h), (0, h). In other words, for all vertices (xi, yi) of the rhombus the following conditions should fulfill: 0 ≤ xi ≤ w and 0 ≤ yi ≤ h.
- Its diagonals are parallel to the axis.

Count the number of such rhombi.

Let us remind you that a rhombus is a quadrilateral whose four sides all have the same length.

## Input Format
The first line contains two integers w and h (1 ≤ w, h ≤ 4000) — the rectangle's sizes.

## Output Format
Print a single number — the number of sought rhombi.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

## Examples
```input
2 2
```
```output
1
```
-----
```input
1 2
```
```output
0
```

## Note
In the first example there exists only one such rhombus. Its vertices are located at points (1, 0), (2, 1), (1, 2), (0, 1).

Now solve the problem and return the code.