Coach Khaled is a swag teacher in HIT (Hag Institute of Technology). However, he has some obsession problems.
Recently, coach Khaled was teaching a course in building 8G networks using TV antennas and programming them with assembly. There are $N$ students (numbered $1$ through $N$) in his class; for some reason, this number is always a multiple of $4$. The final exam has finished and Khaled has all the scores of his $N$ students. For each valid $i$, the score of the $i$-th student is $A_i$; each score is an integer between $0$ and $100$. Currently, the score-grade distribution is as follows:
- grade D for score smaller than $60$
- grade C for score greater or equal to $60$, but smaller than $75$
- grade B for score greater or equal to $75$, but smaller than $90$
- grade A for score greater or equal to $90$
However, coach Khaled is not satisfied with this. He wants exactly $N/4$ students to receive each grade (A, B, C and D), so that the grades are perfectly balanced. The scores cannot be changed, but the boundaries between grades can. Therefore, he wants to choose three integers $x$, $y$ and $z$ and change the grade distribution to the following (note that initially, $x = 60$, $y = 75$ and $z = 90$):
- grade D for score smaller than $x$
- grade C for score greater or equal to $x$, but smaller than $y$
- grade B for score greater or equal to $y$, but smaller than $z$
- grade A for score greater or equal to $z$
Your task is to find thresholds $x$, $y$ and $z$ that result in a perfect balance of grades. If there are multiple solutions, choose the one with the maximum value of $x+y+z$ (because coach Khaled wants seem smarter than his students); it can be proved that there is at most one such solution. Sometimes, there is no way to choose the thresholds and coach Khaled would resign because his exam questions were low-quality.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, if there is no solution, print a single line containing the integer $-1$; otherwise, print a single line containing three space-separated integers $x$, $y$ and $z$.

-----Constraints-----
- $1 \le T \le 1,000$
- $4 \le N \le 100$
- $N$ is divisible by $4$
- $0 \le A_i \le 100$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $5,000$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
6
4
90 25 60 75
8
27 29 92 92 67 67 85 92
4
0 1 2 3
4
100 100 100 100
4
30 30 40 50
4
30 40 40 50

-----Example Output-----
60 75 90
-1
1 2 3
-1
-1
-1

-----Explanation-----
Example case 1: The default distribution is the correct one.
Example case 4: All students have the same score and grade, so there is no way to choose the thresholds and coach Khaled must resign.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	k = n // 4
	a = sorted(map(int, input().split()))
	a60 = (a[k - 1], a[k])
	a75 = (a[2 * k - 1], a[2 * k])
	a90 = (a[3 * k - 1], a[3 * k])
	if a60[0] == a60[1] or a75[0] == a75[1] or a90[0] == a90[1]:
		print(-1)
	else:
		print(a60[1], a75[1], a90[1])


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	k = n // 4
	if l[k - 1] != l[k] and l[2 * k - 1] != l[2 * k] and (l[3 * k - 1] != l[3 * k]):
		print(str(l[k]) + ' ' + str(l[2 * k]) + ' ' + str(l[3 * k]))
	else:
		print('-1')


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	waste = input().split(' ')
	for i in range(n):
		l.append(int(waste[i]))
	l.sort()
	for i in range(n // 4 + 1):
		if i == len(l) // 4:
			x = i
			y = x + len(l) // 4
			z = y + len(l) // 4
			if l[x] == l[x - 1]:
				print(-1)
			elif l[y] == l[y - 1]:
				print(-1)
			elif l[z] == l[z - 1]:
				print(-1)
			else:
				print(str(l[x]) + ' ' + str(l[y]) + ' ' + str(l[z]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = n // 4
	m = []
	for i in l:
		m.append(l.count(i))
	if max(m) > a:
		print(-1)
	else:
		x = a
		y = x + a
		z = y + a
		if l[x] == l[x - 1]:
			print(-1)
		elif l[y] == l[y - 1]:
			print(-1)
		elif l[z] == l[z - 1]:
			print(-1)
		else:
			print(l[x], l[y], l[z])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort(reverse=True)
	x = n // 4 - 1
	y = x + n // 4
	z = y + n // 4
	if a[x] == a[x + 1]:
		print(-1)
		continue
	if a[y] == a[y + 1]:
		print(-1)
		continue
	if a[z] == a[z + 1]:
		print(-1)
		continue
	print(a[z], a[y], a[x])


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = n // 4
	s1 = a[0:i]
	s2 = a[i:2 * i]
	s3 = a[2 * i:3 * i]
	s4 = a[3 * i:4 * i]
	comb = list(set(s1) & set(s2)) + list(set(s2) & set(s3)) + list(set(s3) & set(s4))
	if len(comb) == 0:
		print(s2[0], s3[0], s4[0])
	else:
		print(-1)


for _ in range(int(input())):
	N = int(input())
	L = sorted(map(int, input().split()), reverse=True)
	cut = []
	flag = True
	for i in range(4):
		a = set(L[:N // 4])
		cut.append(min(list(a)))
		L = L[N // 4:]
		for i in a:
			if i in L:
				flag = False
		if not flag:
			break
	if flag:
		print(*cut[2::-1])
	else:
		print(-1)


def func(n, a):
	if a[n // 4] == a[n // 4 - 1]:
		return -1
	else:
		x = a[n // 4]
	if a[2 * n // 4] == a[2 * n // 4 - 1]:
		return -1
	else:
		y = a[2 * n // 4]
	if a[3 * n // 4] == a[3 * n // 4 - 1]:
		return -1
	else:
		z = a[3 * n // 4]
	return str(x) + ' ' + str(y) + ' ' + str(z)
for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	print(func(n, a))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(ele) for ele in input().split()]
	arr.sort()
	x = n // 4
	y = 2 * x
	z = 3 * x
	if arr[x] == arr[x - 1] or arr[y] == arr[y - 1] or arr[z] == arr[z - 1]:
		print('-1')
	else:
		print(arr[x], arr[y], arr[z])


for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	a = n // 4
	b = a + a
	c = b + a
	if arr[a] == arr[a - 1] or arr[b] == arr[b - 1] or arr[c] == arr[c - 1]:
		print(-1)
	else:
		print(arr[a], arr[b], arr[c])


for T in range(int(input())):
	N = int(input())
	A = sorted(list(map(int, input().split())))
	a = N // 4
	b = a + a
	c = b + a
	if A[a] == A[a - 1] or A[b] == A[b - 1] or A[c] == A[c - 1]:
		print(-1)
	else:
		print(A[a], A[b], A[c])


for h in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	x = a[n // 4]
	y = a[n // 2]
	z = a[3 * n // 4]
	if x == a[n // 4 - 1] or y == a[n // 2 - 1] or z == a[3 * n // 4 - 1]:
		print(-1)
	else:
		print(x, y, z)


t = int(input())
for j in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = n // 4
	b = 2 * a
	c = 3 * a
	if l[a] == l[a - 1] or l[b - 1] == l[b] or l[c] == l[c - 1]:
		print('-1')
	else:
		print(l[a], l[b], l[c])


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = n // 4
	l.sort()
	if l[a] == l[a - 1] or l[2 * a] == l[2 * a - 1] or l[3 * a] == l[3 * a - 1]:
		print(-1)
	else:
		print(l[a], l[2 * a], l[3 * a])


def sree(k, n):
	k.sort()
	l = [0, 0, 0]
	if k[n // 2] == k[n // 2 - 1]:
		print(-1)
	else:
		l[1] = k[n // 2]
		if k[3 * n // 4] == k[3 * n // 4 - 1]:
			print(-1)
		else:
			l[2] = k[3 * n // 4]
			if k[n // 4] == k[n // 4 - 1]:
				print(-1)
			else:
				l[0] = k[n // 4]
				print(l[0], l[1], l[2])
t = int(input())
for _ in range(t):
	n = int(input())
	k = list(map(int, input().split()))
	sree(k, n)