1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
New Bakery
Contest: Codeforces Round 953 (Div. 2)
Difficulty rating: 800
Tags: binary search, greedy, math, ternary search

Bob decided to open a bakery. On the opening day, he baked $$$n$$$ buns that he can sell. The usual price of a bun is $$$a$$$ coins, but to attract customers, Bob organized the following promotion:

- Bob chooses some integer $$$k$$$ ($$$0 \le k \le \min(n, b)$$$).
- Bob sells the first $$$k$$$ buns at a modified price. In this case, the price of the $$$i$$$-th ($$$1 \le i \le k$$$) sold bun is $$$(b - i + 1)$$$ coins.
- The remaining $$$(n - k)$$$ buns are sold at $$$a$$$ coins each.

Note that $$$k$$$ can be equal to $$$0$$$. In this case, Bob will sell all the buns at $$$a$$$ coins each.

Help Bob determine the maximum profit he can obtain by selling all $$$n$$$ buns.

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 three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \le n, a, b \le 10^9$$$) — the number of buns, the usual price of a bun, and the price of the first bun to be sold at a modified price.

Output format:
For each test case, output a single integer — the maximum profit that Bob can obtain.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, it is optimal for Bob to choose $$$k = 1$$$. Then he will sell one bun for $$$5$$$ coins, and three buns at the usual price for $$$4$$$ coins each. Then the profit will be $$$5 + 4 + 4 + 4 = 17$$$ coins.

In the second test case, it is optimal for Bob to choose $$$k = 5$$$. Then he will sell all the buns at the modified price and obtain a profit of $$$9 + 8 + 7 + 6 + 5 = 35$$$ coins.

In the third test case, it is optimal for Bob to choose $$$k = 0$$$. Then he will sell all the buns at the usual price and obtain a profit of $$$10 \cdot 10 = 100$$$ coins.

Example input:
7
4 4 5
5 5 9
10 10 5
5 5 11
1000000000 1000000000 1000000000
1000000000 1000000000 1
1000 1 1000

Example output:
17
35
100
45
1000000000000000000
1000000000000000000
500500

Editorial:
If $$$b < a$$$, then the answer is obviously equal to $$$a \cdot n$$$. Otherwise, the profit will be maximized when $$$k = \min(b - a, n)$$$. Indeed, if we take $$$k$$$ larger, then Bob will sell some buns for less than $$$a$$$ coins, which is not profitable. If we take $$$k$$$ smaller, then he will sell some buns for $$$a$$$ coins, although he could have sold them for more. Knowing that $$$a + (a + 1) + \ldots + (b - 1) + b = \frac{a + b}{2} \cdot (b - a + 1)$$$, we can find the answer. It will be equal to $$$\frac{b + (b - k + 1)}{2} \cdot k + (n - k) \cdot a$$$.
Array Coloring
Contest: Codeforces Round 891 (Div. 3)
Difficulty rating: 800
Tags: greedy, math

You are given an array consisting of $$$n$$$ integers. Your task is to determine whether it is possible to color all its elements in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored.

For example, if the array is [$$$1,2,4,3,2,3,5,4$$$], we can color it as follows: [$$$\color{blue}{1},\color{blue}{2},\color{red}{4},\color{blue}{3},\color{red}{2},\color{red}{3},\color{red}{5},\color{red}{4}$$$], where the sum of the blue elements is $$$6$$$ and the sum of the red elements is $$$18$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case begins with a line containing an integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_1,a_2, \dots, a_n$$$ ($$$1 \le a_i \le 50$$$) — the elements of the array $$$a$$$.

Output format:
For each test case, output "YES" (without quotes) if it is possible to color the array in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored, and "NO" otherwise.

You can output "Yes" and "No" in any case (for example, the strings "yES", "yes", and "Yes" will be recognized as correct answers).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first sample is described in the statement.

In the second sample, there are only two colorings $$$[\color{blue}{4},\color{red}{7}]$$$ and $$$[\color{red}{4},\color{blue}{7}]$$$ , but in both cases the parity of sums is different.

In the third sample, you can color $$$[\color{blue}{3},\color{blue}{9},\color{red}{8}]$$$ and $$$12$$$ and $$$8$$$ are both even.

Example input:
7
8
1 2 4 3 2 3 5 4
2
4 7
3
3 9 8
2
1 7
5
5 4 3 2 1
4
4 3 4 5
2
50 48

Example output:
YES
NO
YES
YES
NO
YES
YES

Editorial:
Let's analyze the impact of adding odd or even numbers to a set with sum $$$S$$$:
1. If you add an even element to the set, the parity of $$$S$$$ remains unchanged.
2. If you add an odd element to the set, the parity of $$$S$$$ changes.
Based on this observation, let's focus on the coloring of odd elements in the array. The number of odd elements colored in blue and the number of odd elements colored in red must have the same parity for a valid coloring. This is because we need to divide the odd elements into two parts (blue and red).
To achieve the same parity for both blue and red odd elements, the total number of odd elements in the array must be even. If it is not even, we won't be able to create two sets with the same parity.
Hence, the answer is "YES" if the number of odd elements in the array is even, and "NO" otherwise.
Sum and Product
Contest: Codeforces Round 891 (Div. 3)
Difficulty rating: 1600
Tags: binary search, data structures, math

You have an array $$$a$$$ of length $$$n$$$.

Your task is to answer $$$q$$$ queries: given $$$x,y$$$, find the number of pairs $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n$$$) that both $$$a_i + a_j = x$$$ and $$$a_i \cdot a_j = y$$$.

That is, for the array $$$[1,3,2]$$$ and asking for $$$x=3,y=2$$$ the answer is $$$1$$$:

- $$$i=1$$$ and $$$j=2$$$ fail because $$$1 + 3 = 4$$$ and not $$$3,$$$ also $$$1 \cdot 3=3$$$ and not $$$2$$$;
- $$$i=1$$$ and $$$j=3$$$ satisfies both conditions;
- $$$i=2$$$ and $$$j=3$$$ fail because $$$3 + 2 = 5$$$ and not $$$3,$$$ also $$$3 \cdot 2=6$$$ and not $$$2$$$;

Input format:
The first line contains one integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

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

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

The fourth line of each test case contains the integer $$$q$$$ ($$$1 \le q \le 2\cdot 10^5$$$) — the number of requests.

The next $$$q$$$ lines contain two numbers each $$$x$$$ and $$$y$$$ ($$$1 \le |x|\le 2\cdot 10^9,1\le |y|\le 10^{18}$$$) — request.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$. This is also guaranteed for the sum of $$$q$$$ values.

Output format:
For each test case print a line with $$$q$$$ numbers — the answers to the queries.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
For the first test case, let's analyze each pair of numbers separately:

- pair $$$(a_1,a_2)$$$: $$$a_1 + a_2 = 4$$$, $$$a_1 \cdot a_2 = 3$$$
- pair $$$(a_1,a_3)$$$: $$$a_1 + a_3 = 3$$$, $$$a_1 \cdot a_3 = 2$$$
- pair $$$(a_2,a_3)$$$: $$$a_2 + a_3 = 5$$$, $$$a_2 \cdot a_3 = 6$$$

In the second test case, all combinations of pairs are suitable.

Example input:
3
3
1 3 2
4
3 2
5 6
3 1
5 5
4
1 1 1 1
1
2 1
6
1 4 -2 3 3 3
3
2 -8
-1 -2
7 12

Example output:
1 1 0 0 
6 
1 1 3

Editorial:
The system of equations in the statement resembles Vieta's formula for quadratic equations. If we have $$$$$$ \begin{cases} a_i + a_j = b \\ a_i \cdot a_j = c \end{cases} $$$$$$ the quadratic equation will be $$$x^2 - bx + c = 0$$$, here $$$a_i$$$ and $$$a_j$$$ will be its roots.
To find the roots of the quadratic equation, we can use the discriminant formula, $$$D = b^2 - 4ac$$$. The roots will then be $$$x_1 = \frac{b - \sqrt{D}}{2}$$$ and $$$x_2 = \frac{b + \sqrt{D}}{2}$$$.
Once we have the potential integer values for $$$a_i$$$ and $$$a_j$$$, we can calculate the number of pairs by multiplying the number of occurrences, respectively.
However, remember to consider some special cases:
1. If $$$D < 0$$$, the equation won't have real roots.
2. If $$$D = 0$$$, then $$$x_1 = x_2$$$, the formula for counting pairs in this case is different.
The complexity of this solution is $$$O((n + q) \log n)$$$, using maps to store integer occurrences.
Turtle Puzzle: Rearrange and Negate
Contest: Codeforces Round 929 (Div. 3)
Difficulty rating: 800
Tags: greedy, math, sortings

You are given an array $$$a$$$ of $$$n$$$ integers. You must perform the following two operations on the array (the first, then the second):

1. Arbitrarily rearrange the elements of the array or leave the order of its elements unchanged.
2. Choose at most one contiguous segment of elements and replace the signs of all elements in this segment with their opposites. Formally, you can choose a pair of indices $$$l, r$$$ such that $$$1 \le l \le r \le n$$$ and assign $$$a_i = -a_i$$$ for all $$$l \le i \le r$$$ (negate elements). Note that you may choose not to select a pair of indices and leave all the signs of the elements unchanged.

What is the maximum sum of the array elements after performing these two operations (the first, then the second)?

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The descriptions of the test cases follow.

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

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

Output format:
For each test case, output the maximum sum of the array elements after sequentially performing the two given operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can first rearrange the array to get $$$[3,-2,-3]$$$ (operation 1), then choose $$$l = 2, r = 3$$$ and get the sum $$$3 + -((-2) + (-3)) = 8$$$ (operation 2).

In the second test case, you can do nothing in both operations and get the sum $$$0$$$.

In the third test case, you can do nothing in both operations and get the sum $$$0 + 1 = 1$$$.

In the fourth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 1, r = 1$$$ and get the sum $$$-(-99) = 99$$$ (operation 2).

In the fifth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 2, r = 3$$$ and get the sum $$$10 + -((-2) + (-3)) + 7 = 22$$$ (operation 2).

In the sixth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 1, r = 5$$$ and get the sum $$$-((-1)+(-2)+(-3)+(-4)+(-5))=15$$$ (operation 2).

Example input:
8
3
-2 3 -3
1
0
2
0 1
1
-99
4
10 -2 -3 7
5
-1 -2 -3 -4 -5
6
-41 22 -69 73 -15 -50
12
1 2 3 4 5 6 7 8 9 10 11 12

Example output:
8
0
1
99
22
15
270
78

Editorial:
Neither of the operations change the absolute value of any $$$a_i$$$. Therefore, the maximum answer we can get is $$$|a_1| + |a_2| + \ldots + |a_n|$$$. Now we will show there is a way to obtain this sum.
The way is simple. Firstly use operation 1 to sort the array, so all the negative elements come before the non-negative elements. Then use operation 2 to invert the prefix of negative elements (or not perform the operation if all the elements are non-negative initially). Then we obtain an array of non-negative integers, hence the answer is indeed $$$|a_1| + |a_2| + \ldots + |a_n|$$$.
Turtle Math: Fast Three Task
Contest: Codeforces Round 929 (Div. 3)
Difficulty rating: 800
Tags: implementation, math, number theory

You are given an array $$$a_1, a_2, \ldots, a_n$$$.

In one move, you can perform either of the following two operations:

- Choose an element from the array and remove it from the array. As a result, the length of the array decreases by $$$1$$$;
- Choose an element from the array and increase its value by $$$1$$$.

You can perform any number of moves. If the current array becomes empty, then no more moves can be made.

Your task is to find the minimum number of moves required to make the sum of the elements of the array $$$a$$$ divisible by $$$3$$$. It is possible that you may need $$$0$$$ moves.

Note that the sum of the elements of an empty array (an array of length $$$0$$$) is equal to $$$0$$$.

Input format:
The first line of the input 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$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^4$$$).

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 moves.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, initially the array $$$a = [2, 2, 5, 4]$$$. One of the optimal ways to make moves is:

- remove the current $$$4$$$th element and get $$$a = [2, 2, 5]$$$;

In the second test case, initially, the sum of the array is $$$1+3+2 = 6$$$, which is divisible by $$$3$$$. Therefore, no moves are required. Hence, the answer is $$$0$$$.

In the fourth test case, initially, the sum of the array is $$$1$$$, which is not divisible by $$$3$$$. By removing its only element, you will get an empty array, so its sum is $$$0$$$. Hence, the answer is $$$1$$$.

Example input:
8
4
2 2 5 4
3
1 3 2
4
3 7 6 8
1
1
4
2 2 4 2
2
5 5
7
2 4 8 1 9 3 4
2
4 10

Example output:
1
0
0
1
1
2
1
1

Editorial:
Let's denote the sum of elements as $$$s$$$. If $$$s$$$ is already divisible by $$$3$$$, then the answer is $$$0$$$.
The answer is $$$1$$$ in the following cases:
• If $$$s \bmod 3 = 2$$$, then we can add $$$1$$$ to any element to make the sum divisible by $$$3$$$;
• If there exists an $$$a_i$$$ such that $$$s \bmod 3 = a_i \bmod3$$$, then we can remove such $$$a_i$$$ to make the sum divisible by $$$3$$$.
Otherwise, if $$$s \bmod 3 = 1$$$, we cannot achieve the required sum in one operation. We can increase any element twice, then the sum will increase by $$$2$$$ and become divisible by $$$3$$$.
Turtle Fingers: Count the Values of k
Contest: Codeforces Round 929 (Div. 3)
Difficulty rating: 1100
Tags: brute force, implementation, math, number theory

You are given three positive integers $$$a$$$, $$$b$$$ and $$$l$$$ ($$$a,b,l>0$$$).

It can be shown that there always exists a way to choose non-negative (i.e. $$$\ge 0$$$) integers $$$k$$$, $$$x$$$, and $$$y$$$ such that $$$l = k \cdot a^x \cdot b^y$$$.

Your task is to find the number of distinct possible values of $$$k$$$ across all such ways.

Input format:
The first line contains the integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The following $$$t$$$ lines contain three integers, $$$a$$$, $$$b$$$ and $$$l$$$ ($$$2 \le a, b \le 100$$$, $$$1 \le l \le 10^6$$$) — description of a test case.

Output format:
Output $$$t$$$ lines, with the $$$i$$$-th ($$$1 \le i \le t$$$) line containing an integer, the answer to the $$$i$$$-th test case.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$a=2, b=5, l=20$$$. The possible values of $$$k$$$ (and corresponding $$$x,y$$$) are as follows:

- Choose $$$k = 1, x = 2, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 2, x = 1, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 4, x = 0, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 5, x = 2, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$$$.
- Choose $$$k = 10, x = 1, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$$$.
- Choose $$$k = 20, x = 0, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$$$.

In the second test case, $$$a=2, b=5, l=21$$$. Note that $$$l = 21$$$ is not divisible by either $$$a = 2$$$ or $$$b = 5$$$. Therefore, we can only set $$$x = 0, y = 0$$$, which corresponds to $$$k = 21$$$.

In the third test case, $$$a=4, b=6, l=48$$$. The possible values of $$$k$$$ (and corresponding $$$x,y$$$) are as follows:

- Choose $$$k = 2, x = 1, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$$$.
- Choose $$$k = 3, x = 2, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$$$.
- Choose $$$k = 8, x = 0, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$$$.
- Choose $$$k = 12, x = 1, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$$$.
- Choose $$$k = 48, x = 0, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$$$.

Example input:
11
2 5 20
2 5 21
4 6 48
2 3 72
3 5 75
2 2 1024
3 7 83349
100 100 1000000
7 3 2
2 6 6
17 3 632043

Example output:
6
1
5
12
6
11
24
4
1
3
24

Editorial:
Notice that there are not so many suitable values of $$$x$$$ and $$$y$$$ (since $$$2 \le a, b$$$ and $$$2^{20}=1\ 048\ 576$$$). This allows us to iterate through all suitable pairs of $$$x$$$ and $$$y$$$ and thus find all different suitable $$$k$$$.
Turtle Tenacity: Continual Mods
Contest: Codeforces Round 929 (Div. 3)
Difficulty rating: 1200
Tags: constructive algorithms, greedy, math, number theory, sortings

Given an array $$$a_1, a_2, \ldots, a_n$$$, determine whether it is possible to rearrange its elements into $$$b_1, b_2, \ldots, b_n$$$, such that $$$b_1 \bmod b_2 \bmod \ldots \bmod b_n \neq 0$$$.

Here $$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$. Also, the modulo operations are calculated from left to right. That is, $$$x \bmod y \bmod z = (x \bmod y) \bmod z$$$. For example, $$$2024 \bmod 1000 \bmod 8 = (2024 \bmod 1000) \bmod 8 = 24 \bmod 8 = 0$$$.

Input format:
The first line of the input 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 10^5$$$).

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

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

Output format:
For each test case, output "YES" if it is possible, "NO" 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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, rearranging the array into $$$b = [1, 2, 3, 4, 5, 6]$$$ (doing nothing) would result in $$$1 \bmod 2 \bmod 3 \bmod 4 \bmod 5 \bmod 6 = 1$$$. Hence it is possible to achieve the goal.

In the second test case, the array $$$b$$$ must be equal to $$$[3, 3, 3, 3, 3]$$$, which would result in $$$3 \bmod 3 \bmod 3 \bmod 3 \bmod 3 = 0$$$. Hence it is impossible to achieve the goal.

In the third test case, rearranging the array into $$$b = [3, 2, 2]$$$ would result in $$$3 \bmod 2 \bmod 2 = 1$$$. Hence it is possible to achieve the goal.

Example input:
8
6
1 2 3 4 5 6
5
3 3 3 3 3
3
2 2 3
5
1 1 2 3 7
3
1 2 2
3
1 1 2
6
5 2 10 10 10 2
4
3 6 9 3

Example output:
YES
NO
YES
NO
YES
NO
YES
NO

Editorial:
Sort the array in non-decreasing order. Now, assume $$$a_1 \le a_2 \le \ldots \le a_n$$$.
If $$$a_1 \neq a_2$$$, the minimum is unique. Therefore, place $$$a_1$$$ at the front, and the result after all modulo operations is just $$$a_1 > 0$$$. Hence the answer is yes for this case.
If $$$a_1 = a_2$$$ and there exists some element $$$a_x$$$ such that $$$a_x \not\equiv 0 \pmod {a_1}$$$, then a possible solution is rearranging the array to $$$[a_x, a_1, a_2, \ldots, a_{x-1}, a_{x+1}, \ldots, a_n]$$$. Since $$$a_x \bmod a_1 < a_1$$$, $$$a_x \bmod a_1$$$ is the minimum among the other elements and the result after all modulo operations equals $$$a_x \bmod a_1 > 0$$$. Hence the answer is yes for this case.
Otherwise (if all elements are multiples of the minimum) the answer is no, because any element modulo the minimum equals $$$0$$$, and at least one of the minimums must not be the first element. So after passing through two minimums we are guaranteed to get a $$$0$$$.
Exponential Equation
Contest: TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: constructive algorithms, math

You are given an integer $$$n$$$.

Find any pair of integers $$$(x,y)$$$ ($$$1\leq x,y\leq n$$$) such that $$$x^y\cdot y+y^x\cdot x = n$$$.

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

Each test case contains one line with a single integer $$$n$$$ ($$$1\leq n\leq 10^9$$$).

Output format:
For each test case, if possible, print two integers $$$x$$$ and $$$y$$$ ($$$1\leq x,y\leq n$$$). If there are multiple answers, print any.

Otherwise, print $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the third test case, $$$2^3 \cdot 3+3^2 \cdot 2 = 42$$$, so $$$(2,3),(3,2)$$$ will be considered as legal solutions.

In the fourth test case, $$$5^5 \cdot 5+5^5 \cdot 5 = 31250$$$, so $$$(5,5)$$$ is a legal solution.

Example input:
5
3
7
42
31250
20732790

Example output:
-1
-1
2 3
5 5
3 13

Editorial:
For even $$$n$$$, a key observation is that $$$x=1,y=\dfrac{n}{2}$$$ is always legit.
And for odd $$$n$$$, notice that $$$x^yy+y^xx=xy(x^{y-1}+y^{x-1})$$$. So if $$$x$$$ or $$$y$$$ is an even number, obviously $$$x^y y+y^x x$$$ is an even number. Otherwise if both $$$x$$$ and $$$y$$$ are all odd numbers , $$$x^{y-1}$$$ and $$$y^{x-1}$$$ are all odd numbers, so $$$x^{y-1}+y^{x-1}$$$ is an even number, and $$$x^yy+y^xx$$$ is also an even number. That means $$$x^yy+y^xx$$$ is always even and there's no solution for odd $$$n$$$.
Number Factorization
Contest: TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1100
Tags: greedy, math, number theory

Given an integer $$$n$$$.

Consider all pairs of integer arrays $$$a$$$ and $$$p$$$ of the same length such that $$$n = \prod a_i^{p_i}$$$ (i.e. $$$a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots$$$) ($$$a_i>1;p_i>0$$$) and $$$a_i$$$ is the product of some (possibly one) distinct prime numbers.

For example, for $$$n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 7^1$$$ the array pair $$$a = [2, 7]$$$, $$$p = [2, 1]$$$ is correct, but the pair of arrays $$$a = [4, 7]$$$, $$$p = [1, 1]$$$ is not, because $$$4=2^2$$$ is a product of non-distinct prime numbers.

Your task is to find the maximum value of $$$\sum a_i \cdot p_i$$$ (i.e. $$$a_1\cdot p_1 + a_2\cdot p_2 + \ldots$$$) over all possible pairs of arrays $$$a$$$ and $$$p$$$. Note that you do not need to minimize or maximize the length of the arrays.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case contains only one integer $$$n$$$ ($$$2 \le n \le 10^9$$$).

Output format:
For each test case, print the maximum value of $$$\sum a_i \cdot p_i$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$100 = 10^2$$$ so that $$$a = [10]$$$, $$$p = [2]$$$ when $$$\sum a_i \cdot p_i$$$ hits the maximum value $$$10\cdot 2 = 20$$$. Also, $$$a = [100]$$$, $$$p = [1]$$$ does not work since $$$100$$$ is not made of distinct prime factors.

In the second test case, we can consider $$$10$$$ as $$$10^1$$$, so $$$a = [10]$$$, $$$p = [1]$$$. Notice that when $$$10 = 2^1\cdot 5^1$$$, $$$\sum a_i \cdot p_i = 7$$$.

Example input:
7
100
10
864
130056192
1000000000
2
999999018

Example output:
20
10
22
118
90
2
333333009

Editorial:
First, $$$a_i^{p_i}$$$ is equivalent to the product of $$$a_i^{1}$$$ for $$$p$$$ times, so it is sufficient to set all $$$p_i$$$ to $$$1$$$.
Decomposite $$$n$$$ to some prime factors, greedily choose the most number of distinct prime numbers, the product is the maximum.