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: interview

Starter code:

Solutions:
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, 1e18
    
    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)
    


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]
		else:
			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:
				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

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, 1e18
    
    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)
    


import sys
input = sys.stdin.readline
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:
            print(mx, mx, mx, mx)
        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
            print(res[minj],res[minj],res[minj+1],res[minj+1])

#by Nick "LordVader" Proshin.
import sys
input = sys.stdin.readline
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:
            print(mx, mx, mx, mx)
        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
            print(res[minj],res[minj],res[minj+1],res[minj+1])

#by Nick "LordVader" Proshin
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 list(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 list(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")


#by Nick "LordVader" Proshin
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:
        out.write(str(a[0])+" "+str(a[0])+" "+str(a[0])+" "+str(a[0])+"\n")
    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 stdout, stdin
import collections


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 = collections.Counter(read_int_array(sep=' '))
    prev_el, next_el = None, None
    min_sticks_el = None
    min_sticks = None
    keys = sorted(arr.keys())
    for k in keys:
        if arr[k] > 4:
            arr[k] = 4
        while arr[k] > 1:
            arr[k] -= 2
            prev_el, next_el = next_el, k
            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)
    results.append("{0} {0} {1} {1}".format(min_sticks_el[0], min_sticks_el[1]))

print('\n'.join(results))


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))


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])
 a=min(zip(s,s[1:]),key=lambda a:sum(a)**2/a[0]/a[1])
 r+=['%d %d '%a*2]
print('\n'.join(r))

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
    # print(dub)
    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[j],dub[j+1],prcs(dub[j],dub[j+1]),mn,index)
    print(dub[index],dub[index],dub[index+1],dub[index+1])



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))

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

    t = tc = x = y = a1 = a2 = 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
                    a1, a2 = x, y

            elif tc == 4:
                a1 = a2 = t
                break
        else:
            t = ai
            tc = 1

    super_ans.append(' '.join([str(a1), str(a1), str(a2), str(a2)]))

print('\n'.join(super_ans))

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))


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))