AvtoBus
Contest: Codeforces Round 791 (Div. 2)
Difficulty rating: 900
Tags: brute force, greedy, math, number theory

Spring has come, and the management of the AvtoBus bus fleet has given the order to replace winter tires with summer tires on all buses.

You own a small bus service business and you have just received an order to replace $$$n$$$ tires. You know that the bus fleet owns two types of buses: with two axles (these buses have $$$4$$$ wheels) and with three axles (these buses have $$$6$$$ wheels).

You don't know how many buses of which type the AvtoBus bus fleet owns, so you wonder how many buses the fleet might have. You have to determine the minimum and the maximum number of buses that can be in the fleet if you know that the total number of wheels for all buses is $$$n$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1\,000$$$) — the number of test cases. The following lines contain description of test cases.

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the total number of wheels for all buses.

Output format:
For each test case print the answer in a single line using the following format.

Print two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le y$$$) — the minimum and the maximum possible number of buses that can be in the bus fleet.

If there is no suitable number of buses for the given $$$n$$$, print the number $$$-1$$$ as the answer.

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

Note:
In the first test case the total number of wheels is $$$4$$$. It means that there is the only one bus with two axles in the bus fleet.

In the second test case it's easy to show that there is no suitable number of buses with $$$7$$$ wheels in total.

In the third test case the total number of wheels is $$$24$$$. The following options are possible:

- Four buses with three axles.
- Three buses with two axles and two buses with three axles.
- Six buses with two axles.

So the minimum number of buses is $$$4$$$ and the maximum number of buses is $$$6$$$.

Example input:
4
4
7
24
998244353998244352

Example output:
1 1
-1
4 6
166374058999707392 249561088499561088

Editorial:
Let the number of buses with two axles is $$$x$$$ and the number of buses with three axles is $$$y$$$. Then the equality $$$4x + 6y = n$$$ must be true. If $$$n$$$ is odd, there is no answer, because the left part of the equality is always even. Now we can divide each part of the equality by two: $$$2x + 3y = \frac{n}{2}$$$.
Let's maximize the number of buses. Then we should make $$$x$$$ as large as possible. So, we will get $$$2 + \ldots + 2 + 2 = \frac{n}{2}$$$ if $$$\frac{n}{2}$$$ is even, and $$$2 + \ldots + 2 + 3 = \frac{n}{2}$$$ otherwise. In both cases the number of buses is $$$\left\lfloor \frac{n}{2} \right\rfloor$$$.
Now let's minimize the number of buses. So, we should make $$$y$$$ as large is possible. We will get $$$3 + \ldots + 3 + 3 + 3 = \frac{n}{2}$$$ if $$$\frac{n}{2}$$$ is divisible by $$$3$$$, $$$3 + \ldots + 3 + 3 + 2 = \frac{n}{2}$$$ if $$$n \equiv 2 \pmod 3$$$, and $$$3 + \ldots + 3 + 2 + 2 = \frac{n}{2}$$$ if $$$n \equiv 1 \pmod 3$$$. In all cases the number of buses is $$$\left\lceil \frac{n}{3} \right\rceil$$$.
Also don't forget the case $$$n = 2$$$ — each bus has at least four wheels, so in this case there is no answer.
Time complexity: $$$\mathcal{O}(1)$$$.