Chef has an integer N. It is known that the largest [odd] [divisor] of N does not exceed 10^{5}. 

Determine two non-negative integers A and B such that A^{2} + B^{2} = N, or report that no such pair exists.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single integer N.

------ Output Format ------ 

For each test case, output space-separated A and B such that A^{2} + B^{2} = N or -1 if no such pair exists.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{15}$
- Largest odd divisor of $N$ won't exceed $10^{5}$.

----- Sample Input 1 ------ 
4
100
6
13
4

----- Sample Output 1 ------ 
8 6
-1
2 3
0 2

----- explanation 1 ------ 
Test case $1$: A possible pair $(A, B)$ such that $A^{2} + B^{2} = N$ is $(8, 6)$. Here, $8^{2} + 6^{2} = 64+36 = 100$.

Test case $2$: There is no pair $(A, B)$ such that $A^{2} + B^{2} = N$.

Test case $3$: A possible pair $(A, B)$ such that $A^{2} + B^{2} = N$ is $(2, 3)$. Here, $2^{2} + 3^{2} = 4+9 = 13$

Test case $4$: A possible pair $(A, B)$ such that $A^{2} + B^{2} = N$ is $(0, 2)$. Here, $0^{2} + 2^{2} = 0+4 = 4$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
import math

def make_square(n):
	a = n ** 0.5 // 2
	j = int(n ** 0.5)
	while a <= j:
		temp = n - a * a
		k = temp ** 0.5
		if math.ceil(k) == int(k):
			return (int(k), int(a))
		a += 1
	return (-1,)

def solve(n):
	MAX = 2 * 10 ** 5
	mul = 1
	while n > MAX:
		n /= 4
		mul *= 2
	res = make_square(n)
	if res == (-1,):
		print(-1)
	else:
		print(res[0] * mul, res[1] * mul)

def printf(a):
	if a:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	n = int(input())
	solve(n)


import sys
input = sys.stdin.readline
dp = [False] * 200001
for i in range(500):
	for j in range(i, 500):
		x = i * i + j * j
		if x <= 200000:
			dp[x] = (i, j)

def solve():
	n = int(input())
	counter = 1
	while n % 4 == 0:
		counter *= 2
		n //= 4
	if dp[n] == False:
		return [-1]
	return [dp[n][0] * counter, dp[n][1] * counter]
for _ in range(int(input())):
	print(*solve())


x = [0] * (10 ** 5 + 1)
for i in range(0, 317):
	for j in range(i, 317):
		p = i * i + j * j
		if p > 10 ** 5:
			break
		else:
			x[p] = [i, j]
for _ in range(int(input())):
	n = int(input())
	s = 0
	while n % 2 == 0:
		n = n // 2
		s += 1
	t = x[n]
	if not t:
		print(-1)
		continue
	a = t[1]
	b = t[0]
	if b > a:
		(a, b) = (b, a)
	for i in range(s):
		(a, b) = (a + b, a - b)
	print(a, b)


dp = [0] * 200001
for i in range(500):
	for j in range(i, 500):
		if i * i + j * j <= 200000:
			dp[i * i + j * j] = (i, j)

def solve(n):
	cnt = 1
	while n % 4 == 0:
		n //= 4
		cnt *= 2
	if dp[n] != False:
		return f'{dp[n][0] * cnt} {dp[n][1] * cnt}'
	else:
		return -1
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


import sys
input = sys.stdin.readline
dp = [False] * 200001
for i in range(500):
	for j in range(i, 500):
		if i * i + j * j <= 200000:
			dp[i * i + j * j] = (i, j)
for _ in range(int(input())):
	n = int(input())
	cnt = 1
	while n % 4 == 0:
		n //= 4
		cnt *= 2
	if dp[n] != False:
		print(dp[n][0] * cnt, dp[n][1] * cnt)
	else:
		print(-1)


import sys
from math import isqrt
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	x = 0
	p = n
	while n % 4 == 0:
		n = n // 4
		x += 1
	a = -1
	for i in range(1, isqrt(n) + 1, 2):
		v = n - i * i
		if isqrt(v) ** 2 == v:
			a = i
			break
	if a >= 0:
		print(a * 2 ** x, isqrt(n - a * a) * 2 ** x)
	else:
		print(-1)


from math import sqrt

def helper(a):
	S = 0
	while a % 2 == 0:
		S += 1
		a = a // 2
	if S % 2 == 1:
		S -= 1
		a *= 2
	b = int(sqrt(a))
	for i in range(1, b + 1):
		c = a - i * i
		d = int(sqrt(c))
		if d * d == c:
			return [i << S // 2, d << S // 2]
	return [-1]
test_case = int(input())
for test in range(test_case):
	ref = int(input())
	print(*helper(ref))