Three arrays of the same size are given. Find a triplet such that (maximum – minimum) in that triplet is the minimum of all the triplets. A triplet should be selected in a way such that it should have one number from each of the three given arrays. This triplet is the happiest among all the possible triplets. Print the triplet in decreasing order. If there are 2 or more smallest difference triplets, then the one with the smallest sum of its elements should be displayed.
Example 1:
Input:
N=3
a[] = { 5, 2, 8 }
b[] = { 10, 7, 12 }
c[] = { 9, 14, 6 }  
Output: 7 6 5
Explanation:
The triplet { 5,7,6 }  has difference
(maximum - minimum)= (7-5) =2 which is
minimum of all triplets.  
 
Example 2:
Input:
N=4
a[] = { 15, 12, 18, 9 }
b[] = { 10, 17, 13, 8 }
c[] = { 14, 16, 11, 5 }
Output: 11 10 9
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function smallestDifferenceTriplet() that takes array arr1 , array arr2 ,array arr3 and integer n as parameters and returns the happiest triplet in an array.
 
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:
    def smallestDifferenceTriplet(self,a,b,c,n):
        #code here.
    


Solutions:
from bisect import bisect_left

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = j = k = 0
		ans = [a[0], b[0], c[0]]
		val = max(ans) - min(ans)
		while i < n and j < n and (k < n):
			temp = max(a[i], b[j], c[k]) - min(a[i], b[j], c[k])
			if temp < val or (temp == val and sum(ans) > a[i] + b[j] + c[k]):
				ans = [a[i], b[j], c[k]]
				val = temp
			ll = min(a[i], b[j], c[k])
			if ll == a[i]:
				i += 1
			elif ll == b[j]:
				j += 1
			else:
				k += 1
		ans.sort(reverse=True)
		return ans


from bisect import bisect_left

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		b.sort()
		c.sort()
		ans = sorted([a[0], b[0], c[0]], reverse=True)
		val = max(ans) - min(ans)
		for i in a:
			temp = []
			(ib, ic) = (bisect_left(b, i), bisect_left(c, i))
			if 0 < ib < n:
				k = [b[ib], b[ib - 1]]
			elif ib == 0:
				k = [b[0]]
			else:
				k = [b[-1]]
			if 0 < ic < n:
				g = [c[ic], c[ic - 1]]
			elif ic == 0:
				g = [c[0]]
			else:
				g = [c[-1]]
			for p in k:
				for q in g:
					iter = max(p, q, i) - min(p, q, i)
					if iter < val or (iter == val and i + p + q < sum(ans)):
						val = iter
						ans = sorted([i, p, q], reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		prev = 9999999
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			M = max(a[i], b[j], c[k])
			m = min(a[i], b[j], c[k])
			if m == a[i]:
				i += 1
			elif m == b[j]:
				j += 1
			else:
				k += 1
			if prev > M - m:
				prev = M - m
				x = M
				y = m
				z = sum - (M + m)
		return [x, z, y]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		temp = [a[i], b[j], c[k]]
		val = 1000000
		ans = []
		while i < n and j < n and (k < n):
			temp = [a[i], b[j], c[k]]
			(mi, ma) = (0, 0)
			for idx in range(1, 3):
				if temp[idx] < temp[mi]:
					mi = idx
				if temp[idx] > temp[ma]:
					ma = idx
			if temp[ma] - temp[mi] < val:
				val = temp[ma] - temp[mi]
				ans = temp.copy()
			if mi == 0:
				i += 1
			elif mi == 1:
				j += 1
			else:
				k += 1
		ans.sort(reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(x, y, z) = (a[0], b[0], c[0])
		best = 9999999
		(i, j, k) = (0, 0, 0)
		while i < n and j < n and (k < n):
			mini = min(a[i], b[j], c[k])
			diff = max(a[i], b[j], c[k]) - mini
			if diff < best:
				(x, y, z) = (a[i], b[j], c[k])
				best = diff
			elif mini == a[i]:
				i += 1
			elif mini == b[j]:
				j += 1
			else:
				k += 1
		ans = [x, y, z]
		ans.sort(reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		import bisect

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		dif = 10 ** 8
		while i < n and j < n and (k < n):
			su = a[i] + b[j] + c[k]
			mx = max(a[i], b[j], c[k])
			mi = min(a[i], b[j], c[k])
			if mi == a[i]:
				i += 1
			elif mi == b[j]:
				j += 1
			else:
				k += 1
			if dif > mx - mi:
				dif = mx - mi
				t1 = mx
				t3 = mi
				t2 = su - (mx + mi)
		ans = [t1, t2, t3]
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = j = k = 0
		p = q = r = 0
		summ = a[0] + b[0] + c[0]
		diff = max(a[p], b[q], c[r]) - min(a[p], b[q], c[r])
		while i < n and j < n and (k < n):
			maxi = max(a[i], b[j], c[k])
			mini = min(a[i], b[j], c[k])
			df = maxi - mini
			if df < diff:
				diff = df
				(p, q, r) = (i, j, k)
			elif df == diff:
				csum = sum([a[i], b[j], c[k]])
				if csum < summ:
					(p, q, r) = (i, j, k)
			if a[i] == mini:
				i += 1
			elif b[j] == mini:
				j += 1
			else:
				k += 1
		return sorted([a[p], b[q], c[r]], reverse=1)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		diff = 99999
		while i < n and j < n and (k < n):
			maxele = max(a[i], max(b[j], c[k]))
			minele = min(a[i], min(b[j], c[k]))
			if maxele - minele < diff:
				diff = maxele - minele
				ans = [a[i], b[j], c[k]]
			if minele == a[i]:
				i += 1
			elif minele == b[j]:
				j += 1
			else:
				k += 1
		ans.sort(reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		op = [i for i in range(3)]
		minDiff = float('INF')
		while i < n and j < n and (k < n):
			mi = min(a[i], b[j], c[k])
			ma = max(a[i], b[j], c[k])
			s = sum([a[i], b[j], c[k]])
			d = ma - mi
			if mi == a[i]:
				i = i + 1
			elif mi == b[j]:
				j = j + 1
			elif mi == c[k]:
				k = k + 1
			if d < minDiff:
				minDiff = d
				op[0] = ma
				op[2] = mi
				op[1] = s - (op[0] + op[2])
		return op


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		(a, b, c) = (sorted(a), sorted(b), sorted(c))
		(i, j, k) = (0, 0, 0)
		(p, q, r) = (0, 0, 0)
		(sum, diff) = (0, 123456789)
		while i < n and j < n and (k < n):
			csum = a[i] + b[j] + c[k]
			maximum = max(a[i], b[j], c[k])
			minimum = min(a[i], b[j], c[k])
			cdiff = maximum - minimum
			if minimum == a[i]:
				i += 1
			elif minimum == b[j]:
				j += 1
			else:
				k += 1
			if cdiff < diff:
				diff = cdiff
				sum = csum
				p = maximum
				q = sum - (maximum + minimum)
				r = minimum
		return [p, q, r]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		m = float('inf')
		(i, j, k) = (0, 0, 0)
		while i < n and j < n and (k < n):
			mini = min(a[i], b[j], c[k])
			dif = max(a[i], b[j], c[k]) - mini
			if dif < m:
				res = [a[i], b[j], c[k]]
				m = dif
			if mini == a[i]:
				i += 1
			elif mini == b[j]:
				j += 1
			else:
				k += 1
		res = sorted(res, reverse=True)
		return res


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		op = [i for i in range(3)]
		minDiff = float('INF')
		while i < n and j < n and (k < n):
			minEle = min(a[i], b[j], c[k])
			maxEle = max(a[i], b[j], c[k])
			sumEle = sum([a[i], b[j], c[k]])
			diff = maxEle - minEle
			if minEle == a[i]:
				i += 1
			elif minEle == b[j]:
				j += 1
			elif minEle == c[k]:
				k += 1
			if diff < minDiff:
				minDiff = diff
				op[0] = maxEle
				op[2] = minEle
				op[1] = sumEle - (op[0] + op[2])
		return op


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		ma = float('inf')
		(i, j, k) = (0, 0, 0)
		while i < n and j < n and (k < n):
			mi = min(a[i], b[j], c[k])
			diff = max(a[i], b[j], c[k]) - mi
			if diff < ma:
				res = [a[i], b[j], c[k]]
				ma = diff
			if a[i] == mi:
				i = i + 1
			elif b[j] == mi:
				j = j + 1
			else:
				k = k + 1
		res.sort()
		return res[::-1]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		mini = 100000000.0
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			mn = min(a[i], b[j], c[k])
			mx = max(a[i], b[j], c[k])
			if mn == a[i]:
				i += 1
			elif mn == b[j]:
				j += 1
			else:
				k += 1
			if mini > mx - mn:
				mini = mx - mn
				a1 = mx
				a3 = mn
				a2 = sum - (mx + mn)
				ans = [a1, a2, a3]
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		res_min = 0
		res_max = 0
		res_mid = 0
		i = 0
		j = 0
		k = 0
		diff = 2147483647
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			maxi = max(a[i], max(b[j], c[k]))
			mini = min(a[i], min(b[j], c[k]))
			if mini == a[i]:
				i += 1
			elif mini == b[j]:
				j += 1
			else:
				k += 1
			if diff > maxi - mini:
				diff = maxi - mini
				res_max = maxi
				res_mid = sum - (maxi + mini)
				res_min = mini
		return (res_max, res_mid, res_min)


import sys

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(x, y, z) = (a[0], b[0], c[0])
		res = sys.maxsize
		(i, j, k) = (0, 0, 0)
		while i < n and j < n and (k < n):
			(mini, maxi) = (min(a[i], b[j], c[k]), max(a[i], b[j], c[k]))
			diff = maxi - mini
			if diff < res:
				res = diff
				(x, y, z) = (a[i], b[j], c[k])
			if a[i] == mini:
				i += 1
			elif b[j] == mini:
				j += 1
			else:
				k += 1
		ans = [x, y, z]
		ans.sort(reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort(reverse=True)
		b.sort(reverse=True)
		c.sort(reverse=True)
		triplet = [0, 0, 0]
		diff = float('inf')
		while a and b and c:
			arr = [a[-1], b[-1], c[-1]]
			maxi = max(arr)
			mini = min(arr)
			if maxi - mini < diff:
				diff = maxi - mini
				triplet = arr
			if a[-1] == mini:
				a.pop()
			if b[-1] == mini:
				b.pop()
			if c[-1] == mini:
				c.pop()
		return sorted(triplet, reverse=True)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = j = k = 0
		num1 = num2 = num3 = 0
		diff = float('inf')
		while i < len(a) and j < len(b) and (k < len(c)):
			min_val = min(a[i], b[j], c[k])
			max_val = max(a[i], b[j], c[k])
			sum_val = a[i] + b[j] + c[k]
			if min_val == a[i]:
				i += 1
			elif min_val == b[j]:
				j += 1
			else:
				k += 1
			if diff > max_val - min_val:
				diff = max_val - min_val
				num1 = max_val
				num2 = sum_val - (min_val + max_val)
				num3 = min_val
		return [num1, num2, num3]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = 0
		j = 0
		k = 0
		diff = 99999999999999
		while i < n and j < n and (k < n):
			sum1 = sum([a[i], b[j], c[k]])
			min1 = min([a[i], b[j], c[k]])
			max1 = max([a[i], b[j], c[k]])
			if min1 == a[i]:
				i = i + 1
			elif min1 == b[j]:
				j = j + 1
			else:
				k = k + 1
			if diff > max1 - min1:
				diff = max1 - min1
				a1 = max1
				b1 = sum1 - (max1 + min1)
				c1 = min1
		return [a1, b1, c1]


class Solution:

	def binarysearch(self, arr, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if arr[mid] <= k:
				return self.binarysearch(arr, mid + 1, r, k)
			else:
				return self.binarysearch(arr, l, mid - 1, k)
		return r

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		trip = [0, 100000000]
		for i in range(n):
			newtrip = []
			l = self.binarysearch(b, 0, n - 1, a[i])
			newtrip.append(a[i])
			if l < n:
				if l < n - 1:
					if abs(b[l] - a[i]) > abs(b[l + 1] - a[i]):
						newtrip.append(b[l + 1])
					else:
						newtrip.append(b[l])
				else:
					newtrip.append(b[l])
			l = self.binarysearch(c, 0, n - 1, a[i])
			if l < n:
				if l < n - 1:
					if abs(c[l] - a[i]) > abs(c[l + 1] - a[i]):
						newtrip.append(c[l + 1])
					else:
						newtrip.append(c[l])
				else:
					newtrip.append(c[l])
			if max(trip) - min(trip) > max(newtrip) - min(newtrip):
				trip = newtrip.copy()
			elif max(trip) - min(trip) == max(newtrip) - min(newtrip) and sum(trip) > sum(newtrip):
				trip = newtrip.copy()
		trip.sort(reverse=True)
		return trip


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		ans = float('inf')
		p1 = p2 = p3 = 0
		res1 = res2 = res3 = 0
		while p1 < len(a) and p2 < len(b) and (p3 < len(c)):
			maxx = max(a[p1], b[p2], c[p3])
			minn = min(a[p1], b[p2], c[p3])
			if ans > maxx - minn:
				ans = maxx - minn
				res1 = maxx
				res2 = a[p1] + b[p2] + c[p3] - maxx - minn
				res3 = minn
			if minn == a[p1]:
				p1 += 1
			elif minn == b[p2]:
				p2 += 1
			else:
				p3 += 1
		return [res1, res2, res3]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = j = k = 0
		mini = 10 ** 9
		ans = []
		while i < n and j < n and (k < n):
			x = min(a[i], b[j], c[k])
			y = max(a[i], b[j], c[k])
			if y - x < mini:
				mini = y - x
				ans = [a[i], b[j], c[k]]
			if a[i] == x:
				i += 1
			if b[j] == x:
				j += 1
			if c[k] == x:
				k += 1
		ans.sort(reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = 0
		j = 0
		k = 0
		res_min = 0
		res_max = 0
		res_mid = 0
		diff = 1231231344
		while i < n and j < n and (k < n):
			su = a[i] + b[j] + c[k]
			mins = min([a[i], b[j], c[k]])
			maxs = max([a[i], b[j], c[k]])
			if mins == a[i]:
				i += 1
			elif mins == b[j]:
				j += 1
			else:
				k += 1
			if diff > maxs - mins:
				diff = maxs - mins
				res_max = maxs
				res_min = mins
				res_mid = su - (maxs + mins)
		return (res_max, res_mid, res_min)


def maximum(a, b, c):
	return max(max(a, b), c)

def minimum(a, b, c):
	return min(min(a, b), c)

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		(res_min, res_max, res_mid) = (0, 0, 0)
		diff = 999999999
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			min = minimum(a[i], b[j], c[k])
			max = maximum(a[i], b[j], c[k])
			if min == a[i]:
				i += 1
			elif b[j] == min:
				j += 1
			else:
				k += 1
			if diff > max - min:
				diff = max - min
				res_min = min
				res_max = max
				res_mid = sum - min - max
		return (res_max, res_mid, res_min)
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	ob = Solution()
	ans = ob.smallestDifferenceTriplet(a, b, c, n)
	print(ans[0], ans[1], ans[2])


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		diff = 99999
		while i < n and j < n and (k < n):
			ma = max(a[i], b[j], c[k])
			mi = min(a[i], b[j], c[k])
			if ma - mi < diff:
				diff = ma - mi
				s = a[i] + b[j] + c[k]
				ans = (ma, s - (ma + mi), mi)
			if mi == a[i]:
				i += 1
			elif mi == b[j]:
				j += 1
			else:
				k += 1
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(t1, t2, t3) = (0, 0, 0)
		(i, j, k) = (0, 0, 0)
		diff = 1000000
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			maxi = max(max(a[i], b[j]), c[k])
			mini = min(min(a[i], b[j]), c[k])
			if mini == a[i]:
				i += 1
			elif mini == b[j]:
				j += 1
			else:
				k += 1
			if diff > maxi - mini:
				diff = maxi - mini
				t3 = maxi
				t2 = sum - (maxi + mini)
				t1 = mini
		return [t3, t2, t1]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = 0
		j = 0
		k = 0
		res = []
		diff = float('inf')
		while i < n and j < n and (k < n):
			mini = min(a[i], b[j], c[k])
			maxi = max(a[i], b[j], c[k])
			if maxi - mini < diff:
				diff = maxi - mini
				suma = a[i] + b[j] + c[k]
				res = [maxi, suma - maxi - mini, mini]
			if mini == a[i]:
				i += 1
			elif mini == b[j]:
				j += 1
			else:
				k += 1
		return res


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		difference = float('inf')
		(p1, p2, p3) = (0, 0, 0)
		(x, y, z) = (0, 0, 0)
		while p1 < n and p2 < n and (p3 < n):
			mn = min(a[p1], b[p2], c[p3])
			mx = max(a[p1], b[p2], c[p3])
			diff = mx - mn
			if diff < difference:
				difference = diff
				x = a[p1]
				y = b[p2]
				z = c[p3]
			if a[p1] == mn:
				p1 += 1
			elif b[p2] == mn:
				p2 += 1
			else:
				p3 += 1
		return sorted((x, y, z), reverse=True)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = 0
		j = 0
		k = 0
		Diff = 100000000000.0
		res = []
		while i < n and j < n and (k < n):
			tmp = [a[i], b[j], c[k]]
			MAX = max(tmp)
			MIN = min(tmp)
			diff = MAX - MIN
			if diff < Diff:
				Diff = diff
				res = []
				res += tmp
			if a[i] == MIN:
				i += 1
			elif b[j] == MIN:
				j += 1
			else:
				k += 1
		res.sort(reverse=True)
		return res


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		minDiff = float('inf')
		(first, second, third) = (0, 0, 0)
		a.sort()
		b.sort()
		c.sort()
		ans = []
		while first < n and second < n and (third < n):
			mini = min(a[first], b[second], c[third])
			curr_diff = max(a[first], b[second], c[third]) - mini
			if curr_diff < minDiff:
				ans = [a[first], b[second], c[third]]
			minDiff = min(minDiff, curr_diff)
			if a[first] == mini:
				first += 1
			elif b[second] == mini:
				second += 1
			else:
				third += 1
		ans.sort(reverse=True)
		return ans


import sys

class Solution:

	def smallestDifferenceTriplet(self, arr1, arr2, arr3, n):
		arr1.sort()
		arr2.sort()
		arr3.sort()
		(t1, t2, t3) = (0, 0, 0)
		(i, j, k) = (0, 0, 0)
		diff = 1000000
		while i < n and j < n and (k < n):
			sum = arr1[i] + arr2[j] + arr3[k]
			maxi = max(max(arr1[i], arr2[j]), arr3[k])
			mini = min(min(arr1[i], arr2[j]), arr3[k])
			if diff > maxi - mini:
				diff = maxi - mini
				t3 = maxi
				t2 = sum - (maxi + mini)
				t1 = mini
			if mini == arr1[i]:
				i += 1
			elif mini == arr2[j]:
				j += 1
			else:
				k += 1
		return sorted([t1, t2, t3], reverse=True)


class Solution:

	def smallestDifferenceTriplet(self, A, B, C, n):
		(i, j, k) = (0, 0, 0)
		A.sort()
		B.sort()
		C.sort()
		nA = len(A)
		nB = len(B)
		nC = len(C)
		ans = 2147483647
		diff = 2147483647
		while i < nA and j < nB and (k < nC):
			a = A[i]
			b = B[j]
			c = C[k]
			minE = min(a, b, c)
			if minE == a:
				i += 1
			elif minE == b:
				j += 1
			elif minE == c:
				k += 1
			SUM = a + b + c
			MAX = max(a, b, c)
			MIN = min(a, b, c)
			if diff > MAX - MIN:
				diff = MAX - MIN
				res_max = MAX
				res_mid = SUM - (MAX + MIN)
				res_min = MIN
		return (res_max, res_mid, res_min)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):

		def minimum(x, y, z):
			return min(min(x, y), z)

		def maximum(x, y, z):
			return max(max(x, y), z)
		(res_min, res_max, res_mid) = (0, 0, 0)
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		diff = float('inf')
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			min_val = minimum(a[i], b[j], c[k])
			max_val = maximum(a[i], b[j], c[k])
			if min_val == a[i]:
				i += 1
			elif min_val == b[j]:
				j += 1
			else:
				k += 1
			if max_val - min_val < diff:
				diff = max_val - min_val
				res_min = min_val
				res_max = max_val
				res_mid = sum - (max_val + min_val)
		return [res_max, res_mid, res_min]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		res_min = 0
		res_max = 0
		res_mid = 0
		i = j = k = 0
		diff = 999999999
		while i < n and j < n and (k < n):
			s = a[i] + b[j] + c[k]
			maxe = max(a[i], b[j], c[k])
			mine = min(a[i], b[j], c[k])
			if mine == a[i]:
				i += 1
			elif mine == b[j]:
				j += 1
			else:
				k += 1
			if diff > maxe - mine:
				diff = maxe - mine
				res_max = maxe
				res_mid = s - maxe - mine
				res_min = mine
		return (res_max, res_mid, res_min)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		x = y = z = p = q = r = 0
		a.sort()
		b.sort()
		c.sort()
		diff = 100000
		while p < n and q < n and (r < n):
			mn = min(a[p], b[q], c[r])
			mx = max(a[p], b[q], c[r])
			d = mx - mn
			if d < diff:
				diff = d
				x = a[p]
				y = b[q]
				z = c[r]
			if mn == a[p]:
				p += 1
			elif mn == b[q]:
				q += 1
			else:
				r += 1
		l = []
		l.append(x)
		l.append(y)
		l.append(z)
		l.sort(reverse=True)
		return l


import sys

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = j = k = 0
		rdiff = rsum = sys.maxsize
		while i < n and j < n and (k < n):
			maxnum = max(a[i], b[j], c[k])
			minnum = min(a[i], b[j], c[k])
			sum1 = a[i] + b[j] + c[k]
			midnum = sum1 - maxnum - minnum
			diff = maxnum - minnum
			if diff < rdiff:
				rdiff = diff
				resmax = maxnum
				resmin = minnum
				resmid = midnum
			if minnum == a[i]:
				i = i + 1
			elif minnum == b[j]:
				j = j + 1
			else:
				k = k + 1
		return (resmax, resmid, resmin)


import sys

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		l1 = l2 = l3 = 0
		sum = 0
		diff = sys.maxsize
		maxi = 0
		mini = 0
		res_sum = a[0] + b[0] + c[0]
		res_max = 0
		res_min = 0
		res_mid = 0
		while l1 < n and l2 < n and (l3 < n):
			maxi = max(a[l1], b[l2], c[l3])
			mini = min(a[l1], b[l2], c[l3])
			sum = a[l1] + b[l2] + c[l3]
			if a[l1] == mini:
				l1 += 1
			elif b[l2] == mini:
				l2 += 1
			else:
				l3 += 1
			if diff > maxi - mini:
				diff = maxi - mini
				res_sum = sum
				res_max = maxi
				res_min = mini
		return (res_max, res_sum - res_max - res_min, res_min)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		res = []
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		(fi, fj, fk) = (0, 0, 0)
		diff = 99999999
		while i < n and j < n and (k < n):
			mn = min(a[i], b[j], c[k])
			mx = max(a[i], b[j], c[k])
			sm = a[i] + b[j] + c[k]
			if mx - mn < diff:
				diff = mx - mn
				(fi, fj, fk) = (mn, sm - mx - mn, mx)
			if mn == a[i]:
				i += 1
			if mn == b[j]:
				j += 1
			if mn == c[k]:
				k += 1
		return (fk, fj, fi)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i_a = 0
		i_b = 0
		i_c = 0
		min_diff_triplet = [-1] * 3
		min_diff = 10 ** 5
		for x in range(3 * (n - 1) + 1):
			(val_a, val_b, val_c) = (a[i_a], b[i_b], c[i_c])
			diff = max(val_a, val_b, val_c) - min(val_a, val_b, val_c)
			if diff < min_diff:
				min_diff_triplet = sorted([val_a, val_b, val_c], reverse=True)
				min_diff = diff
			next_a = a[i_a + 1] if i_a < n - 1 else 10 ** 5
			next_b = b[i_b + 1] if i_b < n - 1 else 10 ** 5
			next_c = c[i_c + 1] if i_c < n - 1 else 10 ** 5
			if next_a <= next_b and next_a <= next_c:
				i_a += 1
			elif next_b <= next_a and next_b <= next_c:
				i_b += 1
			elif next_c <= next_a and next_c <= next_b:
				i_c += 1
		return min_diff_triplet


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = 0
		j = 0
		k = 0
		minm = float('inf')
		while i < n and j < n and (k < n):
			triplet = [a[i], b[j], c[k]]
			currMin = min(triplet)
			currMax = max(triplet)
			diff = currMax - currMin
			if diff < minm:
				minm = diff
				curr = list(triplet)
				curr.sort(reverse=True)
			if currMin == a[i]:
				i += 1
			elif currMin == b[j]:
				j += 1
			elif currMin == c[k]:
				k += 1
		return curr


class Solution:

	def maximum(self, a, b, c):
		return max(max(a, b), c)

	def minimum(self, a, b, c):
		return min(min(a, b), c)

	def smallestDifferenceTriplet(self, arr1, arr2, arr3, n):
		arr1.sort()
		arr2.sort()
		arr3.sort()
		res_min = 0
		res_max = 0
		res_mid = 0
		i = 0
		j = 0
		k = 0
		diff = 50
		while i < n and j < n and (k < n):
			sum = arr1[i] + arr2[j] + arr3[k]
			max = self.maximum(arr1[i], arr2[j], arr3[k])
			min = self.minimum(arr1[i], arr2[j], arr3[k])
			if min == arr1[i]:
				i += 1
			elif min == arr2[j]:
				j += 1
			else:
				k += 1
			if diff > max - min:
				diff = max - min
				res_max = max
				res_mid = sum - (max + min)
				res_min = min
		return [res_max, res_mid, res_min]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		merge_sort(a)
		merge_sort(b)
		merge_sort(c)
		i = 0
		j = 0
		k = 0
		diff = 100000000000
		temmax = 0
		temmin = 0
		temmid = 0
		while i < n and j < n and (k < n):
			summ = a[i] + b[j] + c[k]
			mi = min(a[i], b[j], c[k])
			ma = max(a[i], b[j], c[k])
			if mi == a[i]:
				i += 1
			elif mi == b[j]:
				j += 1
			elif mi == c[k]:
				k += 1
			if ma - mi < diff:
				diff = ma - mi
				temmax = ma
				temmin = mi
				temmid = summ - (ma + mi)
		return [temmax, temmid, temmin]

def merge_sort(list1):
	if len(list1) > 1:
		mid = len(list1) // 2
		left_list = list1[:mid]
		right_list = list1[mid:]
		merge_sort(left_list)
		merge_sort(right_list)
		i = 0
		j = 0
		k = 0
		while i < len(left_list) and j < len(right_list):
			if left_list[i] < right_list[j]:
				list1[k] = left_list[i]
				i += 1
				k += 1
			else:
				list1[k] = right_list[j]
				j += 1
				k += 1
		while i < len(left_list):
			list1[k] = left_list[i]
			i += 1
			k += 1
		while j < len(right_list):
			list1[k] = right_list[j]
			j += 1
			k += 1


import sys

class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		diff = sys.maxsize
		a.sort()
		b.sort()
		c.sort()
		ans = []
		i = j = k = 0
		while i < n and j < n and (k < n):
			mini = min(a[i], b[j], c[k])
			maxi = max(a[i], b[j], c[k])
			sum = a[i] + b[j] + c[k]
			if mini == a[i]:
				i += 1
			elif mini == b[j]:
				j += 1
			else:
				k += 1
			if diff > maxi - mini:
				diff = maxi - mini
				a1 = maxi
				a2 = sum - maxi - mini
				a3 = mini
		return [a1, a2, a3]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		results = []
		sums = []
		diff = max(a[0], b[0], c[0]) - min(a[0], b[0], c[0])
		i = 0
		j = 0
		k = 0
		while i < n and j < n and (k < n):
			minimum = min(a[i], b[j], c[k])
			temp = max(a[i], b[j], c[k]) - minimum
			if temp <= diff:
				results.append([a[i], b[j], c[k]])
				diff = temp
				sums.append(a[i] + b[j] + c[k])
			if a[i] == minimum:
				i += 1
			if b[j] == minimum:
				j += 1
			if c[k] == minimum:
				k += 1
		results1 = []
		for i in range(len(results)):
			if max(results[i]) - min(results[i]) <= diff:
				results1.append(results[i])
		if len(results1) == 0:
			res = [a[0], b[0], c[0]]
			res.sort(reverse=True)
			return res
		else:
			res = results1[sums.index(min(sums))]
			res.sort(reverse=True)
			return res


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		i = 0
		j = 0
		k = 0
		m = 1000000000
		ans = [0, 0, 0]
		while i < n and k < n and (j < n):
			temp = [a[i], b[j], c[k]]
			if m > max(temp) - min(temp):
				ans = temp
				m = max(temp) - min(temp)
			if a[i] <= b[j] and a[i] <= c[k]:
				i += 1
			elif b[j] <= c[k] and b[j] <= a[i]:
				j += 1
			else:
				k += 1
		ans.sort(reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		result1 = 0
		result2 = 0
		result3 = 0
		i = 0
		j = 0
		k = 0
		diff = 100000
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			x = max(a[i], b[j], c[k])
			y = min(a[i], b[j], c[k])
			if y == a[i]:
				i += 1
			elif y == b[j]:
				j += 1
			else:
				k += 1
			if diff > x - y:
				diff = x - y
				result3 = sum - (x + y)
				result2 = x
				result1 = y
		return (result2, result3, result1)


class Solution:

	def smallestDifferenceTriplet(self, Arr1, Arr2, Arr3, N):
		ans = []
		Arr1.sort()
		Arr2.sort()
		Arr3.sort()
		(maxo, mino, mido) = (0, 0, 0)
		(i, j, k) = (0, 0, 0)
		(maxoo, minoo, midoo) = (0, 0, 0)
		diff = 1000001
		ludo = 0
		non = 0
		while i < N and j < N and (k < N):
			sumo = Arr1[i] + Arr2[j] + Arr3[k]
			mino = min(Arr1[i], Arr2[j], Arr3[k])
			maxo = max(Arr1[i], Arr2[j], Arr3[k])
			ludo = maxo + mino
			if Arr1[i] == mino:
				i += 1
			elif Arr2[j] == mino:
				j += 1
			else:
				k += 1
			if diff > maxo - mino and non < ludo:
				diff = maxo - mino
				maxoo = maxo
				minoo = mino
				midoo = sumo - (maxo + mino)
				non = ludo
		ans.append(maxoo)
		ans.append(midoo)
		ans.append(minoo)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, arr1, arr2, arr3, n):
		arr1.sort()
		arr2.sort()
		arr3.sort()
		res_min = 0
		res_max = 0
		res_mid = 0
		i = 0
		j = 0
		k = 0
		diff = 2147483647
		while i < n and j < n and (k < n):
			sum = arr1[i] + arr2[j] + arr3[k]
			maxi = max(arr1[i], arr2[j], arr3[k])
			mini = min(arr1[i], arr2[j], arr3[k])
			if mini == arr1[i]:
				i += 1
			elif mini == arr2[j]:
				j += 1
			else:
				k += 1
			if diff > maxi - mini:
				diff = maxi - mini
				res_max = maxi
				res_mid = sum - (maxi + mini)
				res_min = mini
		return (res_max, res_mid, res_min)


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		(i, j, k) = (0, 0, 0)
		prev_diff = None
		prev_sum = None
		a.sort()
		b.sort()
		c.sort()
		while i < n and j < n and (k < n):
			tmp_a = a[i]
			tmp_b = b[j]
			tmp_c = c[k]
			triple_min = min(tmp_a, tmp_b, tmp_c)
			triple_max = max(tmp_a, tmp_b, tmp_c)
			triple_sum = sum([tmp_a, tmp_b, tmp_c])
			curr_diff = triple_max - triple_min
			if prev_diff is None or prev_diff > curr_diff or (prev_diff == curr_diff and prev_sum > triple_sum):
				final_min = triple_min
				final_max = triple_max
				final_mid = triple_sum - final_min - final_max
				prev_diff = curr_diff
				prev_sum = triple_sum
			if triple_min == tmp_a:
				i += 1
			elif triple_min == tmp_b:
				j += 1
			else:
				k += 1
		return [final_max, final_mid, final_min]


class Solution:

	def func(x, y, z):
		mn = min(x, y, z)
		mx = max(x, y, z)
		return mx - mn

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		(a1, b1, c1) = (a[-1], b[-1], c[-1])
		ans = 1000000
		while i < n and j < n and (k < n):
			temp = Solution.func(a[i], b[j], c[k])
			if ans > temp:
				ans = temp
				a1 = a[i]
				b1 = b[j]
				c1 = c[k]
			elif ans == temp:
				temp2 = a[i] + b[j] + c[k]
				temp3 = a1 + b1 + c1
				if temp2 < temp3:
					a1 = a[i]
					b1 = b[j]
					c1 = c[k]
			mn = min(a[i], b[j], c[k])
			if a[i] == mn:
				i += 1
			elif b[j] == mn:
				j += 1
			else:
				k += 1
		ans = [a1, b1, c1]
		ans.sort(reverse=True)
		return ans


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		(i, j, k) = (0, 0, 0)
		(I, J, K) = (-1, -1, -1)
		m = max(a[-1], b[-1], c[-1]) - min(a[0], b[0], c[0])
		while i < n and j < n and (k < n):
			temp = max(a[i], b[j], c[k]) - min(a[i], b[j], c[k])
			if temp < m:
				m = temp
				(I, J, K) = (i, j, k)
			if a[i] <= b[j] and a[i] <= c[k]:
				i += 1
			elif b[j] <= a[i] and b[j] <= c[k]:
				j += 1
			else:
				k += 1
		return sorted([a[I], b[J], c[K]], reverse=True)


class Solution:

	def maximum(self, a1, b1, c1):
		return max(max(a1, b1), c1)

	def minimum(self, a1, b1, c1):
		return min(min(a1, b1), c1)

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		res_max = res_mid = res_min = 0
		diff = float('inf')
		i = j = k = 0
		while i < n and j < n and (k < n):
			sum = a[i] + b[j] + c[k]
			ma = self.maximum(a[i], b[j], c[k])
			mi = self.minimum(a[i], b[j], c[k])
			if mi == a[i]:
				i += 1
			elif mi == b[j]:
				j += 1
			else:
				k += 1
			if diff > ma - mi:
				diff = ma - mi
				res_max = ma
				res_mid = sum - (ma + mi)
				res_min = mi
		return [res_max, res_mid, res_min]


class Solution:

	def smallestDifferenceTriplet(self, a, b, c, n):
		a.sort()
		b.sort()
		c.sort()
		r = 10 ** 6
		r_max = r_min = r_mid = 0
		i = j = k = 0
		while i < n and j < n and (k < n):
			s = a[i] + b[j] + c[k]
			ma = max(a[i], b[j], c[k])
			mi = min(a[i], b[j], c[k])
			if mi == a[i]:
				i += 1
			elif mi == b[j]:
				j += 1
			else:
				k += 1
			if r > ma - mi:
				r = ma - mi
				r_max = ma
				r_mid = s - (ma + mi)
				r_min = mi
		return [r_max, r_mid, r_min]