Given an array arr of size N and an integer K. The task is to find the pair of integers in the array such that their sum is maximum but less than K.
Note:Out of every possible pair, find pair with a maximum absolute difference.
Input:
The first line of input contains an integer T denoting the number of test cases. T testcases follow.
The first line of each test case contains N and K, where N is the number of elements in the array and K is the bound. The second line of each test case contains the array elements.
Output:
Print the pair with the maximum sum less than K.
Your task:
You don't have to take input. Complete the function Max_Sum(), which takes the array, N and K as parameters and returns the pair of integer if exist else return pair of zeros (0,0). The printing is done by the driver code. 
Constraints:
1 ≤ T ≤ 10
0 ≤ N ≤ 10^{5}
0 ≤ K ≤ 10^{6}
0 ≤ arr[i] ≤ 10^{5}
Example:
Input:
2
6 10
2 3 4 6 8 10
6 0
2 3 4 6 8 10
Output:
3 6
0 0
Explanation:
Testcase 1: Pair (3,6) has a maximum sum equals 9 which is less than 10.
Testcase 2: There doesn't exist any pair in the array with a sum less than 0.

Difficulty: EASY
Tags: Data structures
Skill types: Data structures

Starter code:
#User function Template for python3

def Max_Sum(arr,n,k):
    '''
    arr: given array
    n: size of array
    k:  as described in problem
    
    return: pair of ans
    '''

Solutions:
def Max_Sum(arr, n, k):
	arr.sort()
	l = 0
	r = n - 1
	res = [0, 0]
	max_sum = -1
	while l < r:
		sum = arr[l] + arr[r]
		if sum >= k:
			r -= 1
		else:
			if max_sum < sum:
				max_sum = sum
				res = [arr[l], arr[r]]
			l += 1
	return res


def Max_Sum(arr, n, k):
	arr.sort()
	diff = float('inf')
	output = [0, 0]
	j = n - 1
	for i in range(n - 1):
		while j > i and arr[i] + arr[j] >= k:
			j -= 1
		if j <= i:
			break
		if k - arr[i] - arr[j] < diff:
			diff = k - arr[i] - arr[j]
			output = (arr[i], arr[j])
	return output


def Max_Sum(arr, n, k):
	arr.sort()
	ans = 0
	lst = [0, 0]
	l = 0
	r = n - 1
	while l < r:
		sums = arr[l] + arr[r]
		if sums < k:
			if sums > ans:
				lst = [arr[l], arr[r]]
			ans = max(ans, sums)
			l += 1
		else:
			r -= 1
	return lst


def Max_Sum(arr, n, k):
	arr.sort()
	(lo, hi) = (0, len(arr) - 1)
	max_sum = 0
	max_pair = [0, 0]
	while lo < hi:
		pair_sum = arr[lo] + arr[hi]
		if pair_sum < k and pair_sum > max_sum:
			max_sum = pair_sum
			max_pair = [arr[lo], arr[hi]]
		if pair_sum >= k:
			hi -= 1
		if pair_sum < k:
			lo += 1
	return max_pair


def Max_Sum(arr, n, k):
	arr.sort()
	ans = (0, 0)
	sum = 0
	maxsum = 0
	l = 0
	r = n - 1
	while l < r:
		sum = arr[l] + arr[r]
		if sum < k:
			if sum > maxsum:
				ans = (arr[l], arr[r])
			maxsum = max(sum, maxsum)
			l += 1
		else:
			r -= 1
	return ans


def Max_Sum(arr, n, k):
	arr.sort()
	j = n - 1
	i = 0
	lis = []
	s = 0
	m = 0
	summ = 0
	while j > i:
		if arr[i] + arr[j] < k:
			if summ < arr[i] + arr[j]:
				s = arr[i]
				m = arr[j]
			summ = max(summ, arr[i] + arr[j])
			i += 1
		if arr[i] + arr[j] >= k:
			j -= 1
	return (s, m)


def Max_Sum(arr, n, k):
	arr.sort()
	res = [0, 0]
	i = 0
	j = n - 1
	sum = 0
	while i < j:
		if arr[i] + arr[j] < k:
			if arr[i] + arr[j] > sum:
				sum = arr[i] + arr[j]
				res = [arr[i], arr[j]]
			i += 1
		else:
			j -= 1
	return res


def Max_Sum(arr, n, k):
	arr.sort()
	max_val = -1234567
	ans = [0, 0]
	low = 0
	high = n - 1
	while low < high:
		total = arr[low] + arr[high]
		if total < k:
			if total > max_val:
				max_val = total
				ans[0] = arr[low]
				ans[1] = arr[high]
			low += 1
		elif total >= k:
			high -= 1
	return ans


def Max_Sum(arr, n, k):
	arr.sort()
	max_val = 0
	ans = [0, 0]
	low = 0
	high = n - 1
	while low < high:
		total = arr[low] + arr[high]
		if total < k:
			if total > max_val:
				max_val = total
				ans[0] = arr[low]
				ans[1] = arr[high]
			low += 1
		else:
			high -= 1
	return ans


def Max_Sum(nums, n, k):
	l = 0
	r = n - 1
	closest = -1
	pair = (0, 0)
	nums.sort()
	while l < r:
		s = nums[l] + nums[r]
		if s < k:
			if abs(closest - k) > abs(s - k):
				closest = s
				pair = (nums[l], nums[r])
			l += 1
		elif s >= k:
			r -= 1
	return pair


def Max_Sum(arr, n, k):
	arr.sort()
	i = 0
	j = len(arr) - 1
	ans = [0, 0]
	maxi = -10000000000
	while i < j:
		if arr[i] + arr[j] >= k:
			j -= 1
		else:
			if arr[i] + arr[j] > maxi:
				maxi = arr[i] + arr[j]
				ans = [arr[i], arr[j]]
			i += 1
	return ans


def Max_Sum(arr, n, k):
	arr.sort()
	ans = [0, 0]
	curr = 0
	i = 0
	j = n - 1
	while i < j:
		if arr[i] + arr[j] >= k:
			j -= 1
		else:
			if arr[i] + arr[j] > curr:
				curr = arr[i] + arr[j]
				ans = [arr[i], arr[j]]
			i += 1
	return ans


def Max_Sum(arr, n, k):
	arr.sort()
	i = 0
	j = n - 1
	res = 0
	x = 0
	y = 0
	while i < j:
		temp = arr[i] + arr[j]
		if temp < k:
			if temp > res:
				res = temp
				(x, y) = (arr[i], arr[j])
			i += 1
		elif temp >= k:
			j -= 1
	return (x, y)
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		(n, k) = [int(x) for x in input().split()]
		arr = [int(x) for x in input().split()]
		ans = Max_Sum(arr, n, k)
		print(ans[0], ans[1])


def Max_Sum(arr, n, k):
	arr.sort()
	i = 0
	j = n - 1
	m = [0, 0]
	while i < j:
		if arr[j] + arr[i] < k:
			if m[1] + m[0] < arr[j] + arr[i]:
				m = [arr[i], arr[j]]
			i += 1
		else:
			j -= 1
	return m


def Max_Sum(x, n, k):
	x.sort()
	i = 0
	j = len(x) - 1
	maxx = -1
	ab = 0
	ans = [0, 0]
	while i < j:
		ssum = x[i] + x[j]
		if ssum < k:
			if ssum > maxx:
				maxx = ssum
				ab = abs(x[i] - x[j])
				ans = [x[i], x[j]]
			elif ssum == maxx:
				if ab < abs(x[i] - x[j]):
					ab = abs(x[i] - x[j])
					ans = [x[i], x[j]]
			i += 1
		else:
			j -= 1
	return ans


def Max_Sum(arr, n, k):
	arr.sort()
	sum = -1
	s = [0] * 2
	i = 0
	j = n - 1
	while i < j:
		if arr[i] + arr[j] >= k:
			j -= 1
		else:
			if arr[i] + arr[j] > sum:
				sum = arr[i] + arr[j]
				s[0] = arr[i]
				s[1] = arr[j]
			i += 1
	return s


def Max_Sum(arr, n, k):
	arr.sort()
	l = 0
	r = n - 1
	ans = [0, 0]
	while l < r:
		if arr[l] + arr[r] < k:
			if ans[0] + ans[1] < arr[l] + arr[r]:
				ans[0] = arr[l]
				ans[1] = arr[r]
			l += 1
		else:
			r -= 1
	return ans


def Max_Sum(arr, n, k):
	arr.sort()
	pointer1 = 0
	pointer2 = len(arr) - 1
	maxSum = 0
	res1 = 0
	res2 = 0
	while pointer1 < pointer2:
		if arr[pointer1] + arr[pointer2] < k:
			if arr[pointer1] + arr[pointer2] > maxSum:
				maxSum = arr[pointer1] + arr[pointer2]
				res1 = arr[pointer1]
				res2 = arr[pointer2]
			pointer1 += 1
		else:
			pointer2 -= 1
	return [res1, res2]


import sys

def Max_Sum(arr, n, k):
	arr.sort()
	max_value = -1 * sys.maxsize
	start = 0
	end = 0
	p1 = 0
	p2 = len(arr) - 1
	while p1 != p2 and p1 < len(arr) and (p2 < len(arr)) and (p1 < p2):
		if arr[p1] + arr[p2] >= k:
			p2 -= 1
			continue
		elif arr[p1] + arr[p2] > max_value and arr[p1] + arr[p2] < k:
			start = p1
			end = p2
			max_value = arr[p1] + arr[p2]
		p1 += 1
	if max_value == -1 * sys.maxsize:
		return (0, 0)
	return (arr[start], arr[end])


import sys
import bisect

def Max_Sum(arr, n, k):
	arr.sort()
	left = 0
	right = len(arr) - 1
	ans = [0, 0]
	right = bisect.bisect_left(arr, k) - 1
	if right < 0:
		return ans
	res = -sys.maxsize
	while left < right:
		if arr[left] + arr[right] >= k:
			right -= 1
		else:
			newMax = max(res, arr[left] + arr[right])
			if newMax > res:
				ans = [arr[left], arr[right]]
				res = newMax
			left += 1
	return ans


def Max_Sum(arr, n, k):
	if k == 0:
		return (0, 0)
	arr.sort()
	i = 0
	j = len(arr) - 1
	min_diff = 0
	(a, b) = (0, 0)
	while i < j:
		if arr[i] + arr[j] >= k:
			j -= 1
		else:
			if arr[i] + arr[j] > min_diff:
				min_diff = arr[i] + arr[j]
				a = arr[i]
				b = arr[j]
			i += 1
	return (a, b)


def Max_Sum(arr, n, k):
	arr.sort()
	l = 0
	r = n - 1
	maxSum = -10 ** 8
	left = 0
	right = 0
	while l < r:
		s = arr[l] + arr[r]
		if s < k:
			if s > maxSum:
				maxSum = s
				left = arr[l]
				right = arr[r]
			l += 1
		else:
			r -= 1
	return [left, right]


def Max_Sum(arr, n, k):
	res = 0
	pair = (0, 0)
	arr.sort()
	(l, r) = (0, len(arr) - 1)
	while l < r:
		(a, b) = (arr[l], arr[r])
		if a + b < k:
			if a + b > res:
				res = a + b
				pair = (a, b)
			l += 1
		else:
			r -= 1
	return pair


def Max_Sum(arr, n, k):
	diff = 9999
	arr.sort()
	l = 0
	ans = [0, 0]
	r = len(arr) - 1
	while l < r:
		s = arr[l] + arr[r]
		if diff > k - s and s < k:
			ans = [arr[l], arr[r]]
			diff = k - s
		elif s < k:
			l += 1
		else:
			r -= 1
	return ans