You have $n$ sticks of the given lengths.

Your task is to choose exactly four of them in such a way that they can form a rectangle. No sticks can be cut to pieces, each side of the rectangle must be formed by a single stick. No stick can be chosen multiple times. It is guaranteed that it is always possible to choose such sticks.

Let $S$ be the area of the rectangle and $P$ be the perimeter of the rectangle. 

The chosen rectangle should have the value $\frac{P^2}{S}$ minimal possible. The value is taken without any rounding.

If there are multiple answers, print any of them.

Each testcase contains several lists of sticks, for each of them you are required to solve the problem separately.


-----Input-----

The first line contains a single integer $T$ ($T \ge 1$) — the number of lists of sticks in the testcase.

Then $2T$ lines follow — lines $(2i - 1)$ and $2i$ of them describe the $i$-th list. The first line of the pair contains a single integer $n$ ($4 \le n \le 10^6$) — the number of sticks in the $i$-th list. The second line of the pair contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_j \le 10^4$) — lengths of the sticks in the $i$-th list.

It is guaranteed that for each list there exists a way to choose four sticks so that they form a rectangle.

The total number of sticks in all $T$ lists doesn't exceed $10^6$ in each testcase.


-----Output-----

Print $T$ lines. The $i$-th line should contain the answer to the $i$-th list of the input. That is the lengths of the four sticks you choose from the $i$-th list, so that they form a rectangle and the value $\frac{P^2}{S}$ of this rectangle is minimal possible. You can print these four lengths in arbitrary order.

If there are multiple answers, print any of them.


-----Example-----
Input
3
4
7 2 2 7
8
2 8 1 4 8 2 1 5
5
5 5 5 5 5

Output
2 7 7 2
2 2 1 1
5 5 5 5



-----Note-----

There is only one way to choose four sticks in the first list, they form a rectangle with sides $2$ and $7$, its area is $2 \cdot 7 = 14$, perimeter is $2(2 + 7) = 18$. $\frac{18^2}{14} \approx 23.143$.

The second list contains subsets of four sticks that can form rectangles with sides $(1, 2)$, $(2, 8)$ and $(1, 8)$. Their values are $\frac{6^2}{2} = 18$, $\frac{20^2}{16} = 25$ and $\frac{18^2}{8} = 40.5$, respectively. The minimal one of them is the rectangle $(1, 2)$.

You can choose any four of the $5$ given sticks from the third list, they will form a square with side $5$, which is still a rectangle with sides $(5, 5)$.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(NLOG(N))

Starter code:

Solutions:
import sys
input = sys.stdin.readline
out = sys.stdout
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) == 1:
		print(a[0], a[0], a[0], a[0])
	else:
		a.sort()
		g1 = False
		d = {}
		mx = 10001
		for i in a:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] += 1
			if d[i] == 4:
				g1 = True
				if i < mx:
					mx = i
		if g1:
			out.write(str(mx) + ' ' + str(mx) + ' ' + str(mx) + ' ' + str(mx) + '\n')
		else:
			res = []
			for k in d.keys():
				if d[k] >= 2:
					res.append(k)
			m = len(res)
			minj = 0
			for j in range(m - 1):
				if res[j] * res[j + 1] * (res[minj] ** 2 + res[minj + 1] ** 2) > res[minj] * res[minj + 1] * (res[j] ** 2 + res[j + 1] ** 2):
					minj = j
			out.write(str(res[minj]) + ' ' + str(res[minj]) + ' ' + str(res[minj + 1]) + ' ' + str(res[minj + 1]) + '\n')


from sys import stdin

def main():
	input()
	l = stdin.read().splitlines()[1::2]
	for (i, s) in enumerate(l):
		(cnt, x, n) = ([], 0.0, 0)
		for y in sorted(map(float, s.split())):
			if x == y:
				n += 1
			else:
				if n:
					cnt.append((x, n))
				(x, n) = (y, 0)
		if n:
			cnt.append((y, n))
		x = t = 0.0
		for (y, n) in cnt:
			if n > 2:
				u = v = y
				break
			else:
				z = x / y
				if t < z:
					(t, u, v) = (z, x, y)
				x = y
		l[i] = '%d %d %d %d' % (u, u, v, v)
	print('\n'.join(l))
main()


import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	tmp = 10 ** 4
	ans = 10 ** 9
	i = 0
	rec = (0, 0)
	break_bit = 0
	while i < n - 1:
		cnt = 2
		if a[i] == a[i + 1]:
			if ans > a[i] / tmp + tmp / a[i]:
				rec = (tmp, a[i])
				ans = a[i] / tmp + tmp / a[i]
			while i + 2 < n and a[i + 1] == a[i + 2]:
				cnt += 1
				i += 1
				if cnt == 4:
					rec = (a[i], a[i])
					break_bit = 1
					break
			tmp = a[i]
		if break_bit == 1:
			break
		i += 1
	print(rec[0], rec[0], rec[1], rec[1])


ans = []

def main():
	t = int(input())
	for l in range(t):
		n = int(input())
		if n == 4:
			ans.append(input())
		else:
			b = y = num = x = 0
			d = 10 ** 10
			for i in sorted(map(int, input().split())):
				if num == i:
					c += 1
					if c == 2:
						a = b
						b = i
					if a != 0 and a / b + b / a < d:
						d = a / b + b / a
						x = a
						y = b
					elif c == 4:
						x = y = i
						break
				else:
					num = i
					c = 1
			ans.append(str(x) + ' ' + str(y) + ' ' + str(x) + ' ' + str(y))
	return ans
print('\n'.join(main()))


import sys
input = sys.stdin.readline
from collections import Counter
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = Counter(a)
	l = []
	flag = False
	for (k, v) in cnt.items():
		if v >= 4:
			print(k, k, k, k)
			flag = True
			break
		elif v >= 2:
			l.append(k)
	if flag:
		continue
	l.sort()
	for i in range(len(l) - 1):
		(a, b) = (l[i], l[i + 1])
		if i == 0:
			(ans1, ans2) = (a, b)
		elif (ans1 ** 2 + ans2 ** 2) * a * b > (a ** 2 + b ** 2) * ans1 * ans2:
			(ans1, ans2) = (a, b)
	print(ans1, ans1, ans2, ans2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = dd(int)
	a = 0
	for j in l:
		l1[j] += 1
		if l1[j] == 4:
			a = j
	if a:
		print(a, a, a, a)
	else:
		c = 0
		x = 0
		l2 = []
		for j in l1:
			if l1[j] >= 2:
				l2.append(j)
		l2.sort()
		for j in l2:
			c += 1
			if c == 1:
				a = j
			elif c == 2:
				b = j
			elif x / j + j / x < a / b + b / a:
				(a, b) = (x, j)
			x = j
		print(a, a, b, b)


from collections import Counter
import sys
input = sys.stdin.buffer.readline

def print(val):
	sys.stdout.write(str(val) + '\n')

def prog():
	for _ in range(int(input())):
		n = int(input())
		a = Counter(map(int, input().split()))
		work = []
		reached = 0
		for k in a:
			if a[k] >= 4:
				reached = k
				break
			elif a[k] >= 2:
				work.append(k)
		if reached:
			print(4 * (str(k) + ' '))
		else:
			work.sort()
			mn = 10 ** 18
			best = []
			for i in range(len(work) - 1):
				if mn > 4 * (work[i] + work[i + 1]) ** 2 / (work[i] * work[i + 1]):
					mn = 4 * (work[i] + work[i + 1]) ** 2 / (work[i] * work[i + 1])
					best = [work[i], work[i + 1]]
			print(' '.join(map(str, best + best)))
prog()


import sys
T = int(sys.stdin.readline().rstrip())
for i in range(T):
	n = int(sys.stdin.readline().rstrip())
	a = list(map(int, sys.stdin.readline().rstrip().split()))
	rec = []
	a = sorted(a)
	k = 0
	while k < n - 1:
		if a[k] == a[k + 1]:
			rec.append(a[k])
			k += 1
		k += 1
	(ans1, ans2) = (1, 1e+18)
	for j in range(1, len(rec)):
		if ((ans1 + ans2) * 2) ** 2 / (ans1 * ans2) > ((rec[j] + rec[j - 1]) * 2) ** 2 / (rec[j] * rec[j - 1]):
			(ans1, ans2) = (rec[j], rec[j - 1])
	print(ans1, ans2, ans1, ans2)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fun(a, b):
	return (2 * (a + b)) ** 2 / (a * b)
for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	b = []
	i = 0
	while i < n - 1:
		if i < n - 1 and a[i] == a[i + 1]:
			b.append(a[i])
			i += 2
		else:
			i += 1
	m = 10 ** 14
	mi = -1
	for i in range(len(b) - 1):
		curr = fun(b[i], b[i + 1])
		if curr < m:
			m = curr
			mi = i
	print(b[mi], b[mi], b[mi + 1], b[mi + 1])


import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
from collections import deque
from functools import cmp_to_key
import math

def sin():
	return input()

def ain():
	return list(map(int, sin().split()))

def sain():
	return input().split()

def iin():
	return int(sin())
MAX = float('inf')
MIN = float('-inf')
MOD = 1000000007

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	s = set()
	for p in range(2, n + 1):
		if prime[p]:
			s.add(p)
	return s

def readTree(n, m):
	adj = [deque([]) for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = ain()
		adj[u].append(v)
		adj[v].append(u)
	return adj

def main():
	for _ in range(iin()):
		n = iin()
		l = ain()
		c = Counter(l)
		d = deque([])
		val = MAX
		ans = []
		for (k, v) in c.items():
			if v > 1:
				d.append(k)
			if v > 3:
				val = 2
				ans = [k, k]
		tl = sorted(d)
		i = 0
		while i < len(tl) - 1:
			tval = tl[i] / tl[i + 1] + tl[i + 1] / tl[i]
			if tval < val:
				val = tval
				ans = [tl[i], tl[i + 1]]
			i += 1
		print(ans[0], ans[0], ans[1], ans[1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if os.getcwd() == 'D:\\code':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	n = Int()
	arr = array()
	C = Counter(arr)
	arr.sort()
	cur = inf
	ans = []
	a = []
	for i in set(arr):
		if C[i] > 1:
			a.append(i)
	arr = a[:]
	arr.sort()
	for i in range(len(a)):
		a = arr[i]
		b = arr[i - 1]
		now = 4 * (a + b) * (a + b) / (a * b)
		if now < cur:
			cur = now
			ans = [a, a, b, b]
		if C[a] >= 4:
			ans = [a, a, a, a]
			break
	print(*ans)


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
from collections import Counter

def calc(a, b):
	return (2 * (a + b)) ** 2 / (a * b)
n = int(input())
for i in range(n):
	input()
	arr = list(map(int, input().split()))
	arr.sort()
	cnt = Counter()
	doublesticks = list()
	for v in arr:
		if cnt[v] == 1:
			doublesticks.append(v)
			cnt[v] = 0
		else:
			cnt[v] = 1
	ans = calc(doublesticks[1], doublesticks[0])
	idx = 0
	for i in range(len(doublesticks) - 1):
		res = calc(doublesticks[i + 1], doublesticks[i])
		if res < ans:
			ans = res
			idx = i
	print(doublesticks[idx], doublesticks[idx], doublesticks[idx + 1], doublesticks[idx + 1])


import sys
from collections import *
l = sys.stdin.readlines()[2::2]
r = []
for a in l:
	a = Counter(map(int, a.split()))
	s = sorted([k for k in a if a[k] > 1] + [k for k in a if a[k] > 3])
	r += ['%d %d ' % min(zip(s, s[1:]), key=lambda a: sum(a) ** 2 / a[0] / a[1]) * 2]
print(*r)


import sys
from collections import Counter
from bisect import bisect as br, bisect_left as bl
readline = sys.stdin.readline
T = int(readline())
inf = 10 ** 9
for _ in range(T):
	N = int(readline())
	S = list(map(int, readline().split()))
	C = Counter(S)
	K2 = [k for (k, v) in C.items() if v >= 2]
	K4 = [k for (k, v) in C.items() if v >= 4]
	ans = (None, None)
	val = inf
	if K4:
		ans = (K4[0], K4[0])
	else:
		K2.sort()
		L = len(K2)
		K2 = [inf] + K2 + [inf]
		for i in range(1, L + 1):
			a = K2[i]
			(b, c) = (K2[i - 1], K2[i + 1])
			if b / a + a / b < val:
				ans = (a, b)
				val = b / a + a / b
			if c / a + a / c < val:
				ans = (a, c)
				val = c / a + a / c
	sys.stdout.write('{} {} {} {}\n'.format(ans[0], ans[0], ans[1], ans[1]))


import sys
f = sys.stdin
out = sys.stdout

def fun(l, b):
	return (2 * (l + b)) ** 2 / (l * b)
t = int(f.readline().rstrip('\r\n'))
for _ in range(t):
	n = int(f.readline().rstrip('\r\n'))
	a = list(map(int, f.readline().rstrip('\r\n').split()))
	d = {}
	arr = []
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
			arr.append(i)
	arr.sort()
	mi = float('inf')
	tmp = -1
	(l1, b1) = (-1, -1)
	for i in range(len(arr)):
		if tmp == -1:
			if d[arr[i]] >= 4:
				tmp = arr[i]
				pmi = mi
				mi = min(mi, fun(arr[i], arr[i]))
				if pmi != mi:
					(l1, b1) = (arr[i], arr[i])
			elif d[arr[i]] >= 2:
				tmp = arr[i]
		elif d[arr[i]] >= 4:
			tmp = arr[i]
			pmi = mi
			mi = min(mi, fun(arr[i], arr[i]))
			if pmi != mi:
				(l1, b1) = (arr[i], arr[i])
		elif d[arr[i]] >= 2:
			pmi = mi
			mi = min(mi, fun(tmp, arr[i]))
			if pmi != mi:
				(l1, b1) = (tmp, arr[i])
			tmp = arr[i]
	out.write(str(l1) + ' ' + str(l1) + ' ' + str(b1) + ' ' + str(b1) + '\n')


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	for item in arr:
		if item in freq:
			freq[item] += 1
		else:
			freq[item] = 1
	sticks = []
	for item in arr:
		if freq[item] >= 2:
			sticks.append(item)
			freq[item] -= 2
	sticks.sort()
	ans = float('inf')
	lens = len(sticks)
	pair = [-1, -1, -1, -1]
	for (idx, i) in enumerate(sticks):
		if idx == 0:
			res = (2 * (i + sticks[idx + 1])) ** 2 / (i * sticks[idx + 1])
			if res < ans:
				pair[0] = i
				pair[1] = sticks[idx + 1]
				pair[2] = i
				pair[3] = sticks[idx + 1]
				ans = res
		elif idx == lens - 1:
			res = (2 * (i + sticks[idx - 1])) ** 2 / (i * sticks[idx - 1])
			if res < ans:
				pair[0] = i
				pair[1] = sticks[idx - 1]
				pair[2] = i
				pair[3] = sticks[idx - 1]
				ans = res
		else:
			res = (2 * (i + sticks[idx + 1])) ** 2 / (i * sticks[idx + 1])
			if res < ans:
				pair[0] = i
				pair[1] = sticks[idx + 1]
				pair[2] = i
				pair[3] = sticks[idx + 1]
				ans = res
			res = (2 * (i + sticks[idx - 1])) ** 2 / (i * sticks[idx - 1])
			if res < ans:
				pair[0] = i
				pair[1] = sticks[idx - 1]
				pair[2] = i
				pair[3] = sticks[idx - 1]
				ans = res
	print(*pair)


from sys import stdout, stdin

def read():
	return stdin.readline().rstrip('\n')

def read_array(sep=None, maxsplit=-1):
	return read().split(sep, maxsplit)

def read_int():
	return int(read())

def read_int_array(sep=None, maxsplit=-1):
	return [int(a) for a in read_array(sep, maxsplit)]

def write(*args, **kwargs):
	sep = kwargs.get('sep', ' ')
	end = kwargs.get('end', '\n')
	stdout.write(sep.join((str(a) for a in args)) + end)

def write_array(array, **kwargs):
	sep = kwargs.get('sep', ' ')
	end = kwargs.get('end', '\n')
	stdout.write(sep.join((str(a) for a in array)) + end)

def f(a, b):
	return a / b + b / a
n = read_int()
results = []
for _ in range(n):
	read_int()
	arr = sorted(read_int_array(sep=' '))
	i = 0
	len_arr_minus_one = len(arr) - 1
	(prev_el, next_el) = (None, None)
	min_sticks_el = None
	min_sticks = None
	while i < len_arr_minus_one:
		if arr[i] == arr[i + 1]:
			(prev_el, next_el) = (next_el, arr[i])
			i += 2
			if prev_el and next_el:
				if not min_sticks_el:
					min_sticks_el = (prev_el, next_el)
					min_sticks = f(prev_el, next_el)
					continue
				current_value = f(prev_el, next_el)
				if min_sticks > current_value:
					min_sticks = current_value
					min_sticks_el = (prev_el, next_el)
		else:
			i += 1
	results.append('{0} {0} {1} {1}'.format(min_sticks_el[0], min_sticks_el[1]))
print('\n'.join(results))


from functools import cmp_to_key
from math import *
import sys
input = sys.stdin.readline

def comp(a, b, s):
	if len(s) == 0:
		return True
	return 4 * (s[0] + s[1]) ** 2 * a * b > 4 * (a + b) ** 2 * s[0] * s[1]

def main():
	t = int(input())
	for i in range(t):
		sticks = int(input())
		a = [int(x) for x in input().split(' ')]
		m = {}
		for i in a:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		a = []
		for (k, v) in m.items():
			if v == 2 or v == 3:
				a.append(k)
			elif v >= 4:
				a.append(k)
				a.append(k)
		a = sorted(a)
		sticks = []
		for i in range(len(a) - 1):
			(x, y) = (a[i], a[i + 1])
			if comp(x, y, sticks):
				sticks = [x, y]
		print(sticks[0], ' ', sticks[0], ' ', sticks[1], ' ', sticks[1])
main()


super_ans = []
for i in range(int(input())):
	n = input()
	if n == '4':
		super_ans.append(input())
		continue
	elif n == '5':
		a = sorted(map(int, input().split()))
		if a[0] == a[1] and a[2] == a[3]:
			super_ans.append(' '.join([str(a[0]), str(a[0]), str(a[2]), str(a[2])]))
		elif a[0] == a[1] and a[3] == a[4]:
			super_ans.append(' '.join([str(a[0]), str(a[0]), str(a[3]), str(a[3])]))
		else:
			super_ans.append(' '.join([str(a[-1]), str(a[-1]), str(a[-3]), str(a[-3])]))
		continue
	d = 10 ** 9
	ans = []
	t = tc = x = y = 0
	for ai in sorted(map(int, input().split())):
		if t == ai:
			tc += 1
			if tc == 2:
				x = y
				y = ai
				if x and y / x < d:
					d = y / x
					ans = [x, y]
			elif tc == 4:
				ans = [t, t]
				break
		else:
			t = ai
			tc = 1
	super_ans.append(' '.join(map(str, ans * 2)))
print('\n'.join(super_ans))


import sys
t = int(sys.stdin.readline())
arrz = []
for l in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	arr.sort()
	flag = 0
	arr2 = []
	dict1 = {}
	for i in range(n):
		try:
			dict1[arr[i]] += 1
			if dict1[arr[i]] == 2:
				arr2.append(arr[i])
				dict1[arr[i]] = 0
		except:
			KeyError
			dict1[arr[i]] = 1
	fans = arr2[1] / arr2[0]
	index = 0
	for i in range(len(arr2) - 1):
		if arr2[i + 1] / arr2[i] < fans:
			fans = arr2[i + 1] / arr2[i]
			index = i
	arrz.append('%d %d %d %d' % (arr2[index], arr2[index], arr2[index + 1], arr2[index + 1]))
print('\n'.join(arrz))


import sys
rd = lambda : sys.stdin.readline().rstrip()
t = int(rd())
for _ in range(t):
	n = int(rd())
	a = list(map(int, rd().split()))
	b = []
	(res_a, res_b) = (1, 1e+18)
	a = sorted(a)
	i = 0
	while i < n - 1:
		if a[i] == a[i + 1]:
			b.append(a[i])
			i += 1
		i += 1
	p2s = lambda x, y: (x + y) ** 2 / (x * y)
	for i in range(len(b) - 1):
		if p2s(res_a, res_b) > p2s(b[i], b[i + 1]):
			(res_a, res_b) = (b[i], b[i + 1])
	print(res_a, res_a, res_b, res_b)


from collections import Counter
from sys import stdin

def get_ans_min(a, b):
	return (2 * (a + b)) ** 2 / (a * b)

def get_ans(list_):
	C = Counter(list_)
	m = max(C.values())
	if m >= 4:
		e = [el for el in C.keys() if C[el] == m][0]
		return f'{e} {e} {e} {e}'
	key = sorted((el for el in C.keys() if C[el] > 1))
	ans = [get_ans_min(key[i], key[i + 1]) for i in range(len(key) - 1)]
	ind = ans.index(min(ans))
	(a, b) = (key[ind], key[ind + 1])
	return f'{a} {a} {b} {b}'
ans = list(map(get_ans, list(list((map(int, el.split()) for el in stdin.readlines()[2::2])))))
print('\n'.join(ans))


from collections import defaultdict
from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dd = defaultdict(int)
	for i in range(n):
		dd[a[i]] += 1
	l = []
	for aa in a:
		if dd[aa] >= 2:
			l.append(aa)
			dd[aa] -= 2
	l.sort()
	ans = [-1, -1, -1, -1]
	m = 10 ** 18
	for i in range(len(l) - 1):
		x = 4 * (l[i] + l[i + 1]) ** 2 / (l[i] * l[i + 1])
		if x < m:
			ans = [l[i], l[i], l[i + 1], l[i + 1]]
			m = x
	print(*ans)


import sys, os, io
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from sys import stdin
import math

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	n = ii()
	l = li()
	l1 = l[:]
	arr = defaultdict(lambda : 0)
	for i in l:
		arr[i] += 1
	l = []
	graterthan4 = 0
	isgraterthan4 = False
	for i in list(arr.keys()):
		if arr[i] >= 4:
			isgraterthan4 = True
			graterthan4 = i
		if arr[i] >= 2:
			l.append(i)
	n = len(l)
	l.sort()
	m = 1000000000000
	mi = []
	for i in range(n - 1):
		a = l[i]
		b = l[i + 1]
		if a / b + b / a < m:
			m = a / b + b / a
			mi = [a, b]
	if isgraterthan4 == True:
		print(graterthan4, graterthan4, graterthan4, graterthan4)
	else:
		(a, b) = mi
		print(a, a, b, b)


import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
	n = int(input())
	d = {}
	lens = []
	nums = list(map(int, input().strip().split()))
	for num in nums:
		d[num] = d.get(num, 0) + 1
		if d[num] == 2:
			lens.append(num)
			d[num] = 0
	lens = sorted(lens)
	(a, b) = (lens[0], lens[1])
	mmin = float('inf')
	for i in range(1, len(lens)):
		if lens[i] / lens[i - 1] < mmin:
			mmin = lens[i] / lens[i - 1]
			a = lens[i]
			b = lens[i - 1]
	print(a, a, b, b)


import sys
read = lambda : sys.stdin.readline().strip()
prcs = lambda x, y: (x + y) ** 2 / (x * y)
n = int(read())
for i in range(0, n):
	t = int(read())
	a = list(map(int, read().split()))
	a.sort()
	dub = []
	ind = 0
	while ind < t - 1:
		if a[ind] == a[ind + 1]:
			dub.append(a[ind])
			ind += 1
		ind += 1
	mn = prcs(dub[0], dub[1])
	index = 0
	for j in range(0, len(dub) - 1):
		if mn > prcs(dub[j], dub[j + 1]):
			mn = prcs(dub[j], dub[j + 1])
			index = j
	print(dub[index], dub[index], dub[index + 1], dub[index + 1])


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
from collections import Counter
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	C = Counter(A)
	B = []
	for (k, v) in C.items():
		if v >= 4:
			B.append(k)
			B.append(k)
		elif v >= 2:
			B.append(k)
	B.sort()
	l = len(B)
	m = 10 ** 18
	ans = [-1, -1, -1, -1]
	for i in range(l - 1):
		(x, y) = (B[i], B[i + 1])
		temp = 4 * (x + y) ** 2 / (x * y)
		if temp < m:
			m = temp
			ans = [x, x, y, y]
	print(*ans)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = ri()
	for _ in range(tc):
		n = ri()
		a = ria()
		d = Counter(a)
		a = sorted(list(set(a)))
		s = []
		c = 0
		for i in a:
			if d[i] >= 4:
				c = 1
				print(i, i, i, i)
				break
			if d[i] >= 2:
				s.append(i)
		if c == 0:
			lx = 9999999999999999999999999999999
			bx = 1
			for i in range(len(s) - 1):
				l = s[i + 1]
				b = s[i]
				if l * bx < lx * b:
					lx = l
					bx = b
			print(lx, lx, bx, bx)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	d = dict()
	c = []
	for j in range(n):
		if b[j] in d.keys():
			d[b[j]] += 1
			if d[b[j]] % 2 == 0:
				c.append(b[j])
		else:
			d[b[j]] = 1
	c.sort()
	j = 0
	m = 10000000000
	while j < len(c) - 1:
		e = c[j + 1] / c[j] + c[j] / c[j + 1]
		if e < m:
			m = e
			p = c[j]
			q = c[j + 1]
		j += 1
	print(p, p, q, q)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set()
	r = 0
	l.sort()
	l.append(-1)
	c = 1
	a = []
	for j in range(1, n + 1):
		if l[j - 1] == l[j]:
			c += 1
		else:
			if c >= 1:
				for k in range(c // 2):
					a.append(l[j - 1])
			c = 1
	m = a[0]
	ma = a[1]
	r = a[0] / a[1] + a[1] / a[0]
	for j in range(2, len(a)):
		s = a[j - 1] / a[j] + a[j] / a[j - 1]
		if s < r:
			r = s
			m = a[j - 1]
			ma = a[j]
	print(m, m, ma, ma)


import sys
from collections import defaultdict
out = sys.stdout
t = int(sys.stdin.readline())
while t:
	n = int(sys.stdin.readline())
	dic = defaultdict(lambda : 0, {})
	ls = list(sorted(list(map(int, sys.stdin.readline().split())), reverse=True))
	st = set()
	f = 1
	for i in ls:
		dic[i] += 1
		if dic[i] == 4:
			f = 0
			out.write(str(i) + ' ' + str(i) + ' ' + str(i) + ' ' + str(i) + '\n')
			break
	if not f:
		t -= 1
		f = 1
		continue
	for i in ls:
		if dic[i] >= 2:
			st.add(i)
	st = list(sorted(st, reverse=True))
	ln = len(st)
	mn = 4 * (st[0] + st[1]) ** 2 / (st[0] * st[1])
	(a, b, c, d) = (st[1], st[1], st[0], st[0])
	for i in range(1, ln - 1):
		if 4 * (st[i] + st[i + 1]) ** 2 / (st[i] * st[i + 1]) < mn:
			(a, b, c, d) = (st[i], st[i], st[i + 1], st[i + 1])
			mn = 4 * (st[i] + st[i + 1]) ** 2 / (st[i] * st[i + 1])
	out.write(str(a) + ' ' + str(b) + ' ' + str(c) + ' ' + str(d) + '\n')
	t -= 1


queries = int(input())
output = []
for i in range(queries):
	numCount = input()
	if numCount == '4':
		output.append(input())
	else:
		if numCount == '5':
			l = sorted(map(int, input().split()))
			(x, y) = (l[1], l[3])
		else:
			lastNum = b = x = y = 0
			d = 10 ** 12
			for num in sorted(map(int, input().split())):
				if num == lastNum:
					count += 1
					if count == 2:
						a = b
						b = num
						if a and b / a < d:
							d = b / a
							x = a
							y = b
					elif count == 4:
						x = y = num
						break
				else:
					lastNum = num
					count = 1
		output.append(str(x) + ' ' + str(x) + ' ' + str(y) + ' ' + str(y))
print('\n'.join(output))


import sys
from collections import Counter
input = sys.stdin.readline
testcase = int(sys.stdin.readline())
A = [list(map(int, input().split())) for i in range(testcase * 2)]
for t in range(testcase):
	counter = Counter(A[t * 2 + 1])
	LIST = []
	for c in counter:
		if counter[c] >= 4:
			print(c, c, c, c)
			break
		elif counter[c] >= 2:
			LIST.append(c)
	else:
		LIST.sort()
		ANS = [LIST[0], LIST[1], LIST[1] / LIST[0]]
		for i in range(2, len(LIST)):
			if LIST[i] / LIST[i - 1] < ANS[2]:
				ANS = [LIST[i - 1], LIST[i], LIST[i] / LIST[i - 1]]
		print(ANS[0], ANS[0], ANS[1], ANS[1])


import sys
import io, os
import math
from heapq import *
gcd = math.gcd
sqrt = math.sqrt
ceil = math.ceil
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def print(x, end):
	sys.stdout.write(str(x) + end)

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f

def ind(ch):
	return ord(ch) - ord('a')

def cleanarr(arr):
	n = len(arr)
	arr.sort()
	c = []
	curr = [arr[0], 1]
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			if curr[1] >= 2:
				c.append(curr)
			curr = [arr[i + 1], 1]
		else:
			curr[1] += 1
	if curr[1] >= 2:
		c.append(curr)
	return c

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		g = arr[0]
		c = cleanarr(arr)
		if n >= 40000:
			f = 0
			for i in range(len(c)):
				if c[i][1] >= 4:
					f = c[i][0]
					break
			print(f, ' ')
			print(f, ' ')
			print(f, ' ')
			print(f, '\n')
			continue
		mi = 10 ** 18
		pair = [-1, -1]
		for i in range(len(c)):
			if c[i][1] >= 4:
				pair = [c[i][0], c[i][0]]
				break
			if i == len(c) - 1:
				break
			a = c[i][0]
			b = c[i + 1][0]
			if mi == 10 ** 18:
				pair = [a, b]
				mi = 0
				continue
			if (pair[0] + pair[1]) ** 2 * a * b - (a + b) ** 2 * pair[0] * pair[1] > 0:
				pair = [a, b]
		print(pair[0], ' ')
		print(pair[0], ' ')
		print(pair[1], ' ')
		print(pair[1], '\n')
main()


from sys import stdin, stdout
T = int(stdin.readline())
ans = []
for cc in range(0, T):
	n = int(stdin.readline())
	a = [int(x) for x in stdin.readline().split()]
	a.sort()
	a.append(1061109567)
	res = [0, 0, 1, 1]
	pre = 0
	cnt = 0
	for i in a:
		if i == pre:
			cnt += 1
		else:
			if cnt >= 4:
				res = [pre, pre, pre, pre]
				break
			cnt = 1
		pre = i
	if res[0] == 0:
		pre = 0
		val = 0
		for i in a:
			if i == pre and i != val:
				if val * res[-1] > res[0] * i:
					res = [val, val, i, i]
				val = i
			pre = i
	ans.append(' '.join([str(x) for x in res]))
stdout.write('\n'.join(ans) + '\n')


from sys import stdout, stdin

def read():
	return stdin.readline().rstrip('\n')

def f(a, b):
	return a / b + b / a
results = []
for _ in range(int(read())):
	read()
	arr = sorted(map(int, read().split()))
	i = 0
	len_arr_minus_one = len(arr) - 1
	(prev_el, next_el) = (None, None)
	min_sticks_el = None
	min_sticks = None
	while i < len_arr_minus_one:
		if arr[i] == arr[i + 1]:
			(prev_el, next_el) = (next_el, arr[i])
			i += 2
			if prev_el and next_el:
				if not min_sticks_el:
					min_sticks_el = (prev_el, next_el)
					min_sticks = f(prev_el, next_el)
					continue
				current_value = f(prev_el, next_el)
				if min_sticks > current_value:
					min_sticks = current_value
					min_sticks_el = (prev_el, next_el)
		else:
			i += 1
	results.append('{0} {0} {1} {1}'.format(min_sticks_el[0], min_sticks_el[1]))
stdout.write('\n'.join(results) + '\n')


import sys
from array import array
from collections import Counter

def readline():
	return sys.stdin.buffer.readline().decode('utf-8')
t = int(readline())
ans = [''] * t
for i in range(t):
	n = int(readline())
	cnt = Counter(map(int, readline().split()))
	keys = sorted((k for k in cnt.keys() if cnt[k] >= 2))
	(ans1, ans2) = (-1, 10 ** 9)
	for j in range(len(keys)):
		if cnt[keys[j]] >= 4:
			ans1 = keys[j]
			ans2 = keys[j]
			break
		if j < len(keys) - 1:
			if ans1 * keys[j + 1] < ans2 * keys[j]:
				ans1 = keys[j]
				ans2 = keys[j + 1]
	ans[i] = f'{ans1} {ans1} {ans2} {ans2}'
sys.stdout.buffer.write('\n'.join(ans).encode('utf-8'))


from __future__ import print_function
from itertools import permutations as perm
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()
for _ in range(t):
	(n,) = gil()
	a = gil()
	f = Counter(a)
	a = []
	(ai, bi) = (1, 1)
	ans = inf
	for v in f:
		fi = f[v]
		if fi >= 2:
			a.append(v)
			if fi >= 4:
				(ai, bi, ans) = (v, v, 1)
				break
	if ans != 1:
		a.sort()
		for i in range(1, len(a)):
			if a[i] / a[i - 1] < ans:
				(ai, bi, ans) = (a[i], a[i - 1], a[i] / a[i - 1])
	print(ai, ai, bi, bi)