Given an array $a$ of length $n$ and an integer $k$, you are tasked to find any two numbers $l$ and $r$ ($l \leq r$) such that:

For each $x$ $(l \leq x \leq r)$, $x$ appears in $a$ at least $k$ times (i.e. $k$ or more array elements are equal to $x$).

The value $r-l$ is maximized.

If no numbers satisfy the conditions, output -1.

For example, if $a=[11, 11, 12, 13, 13, 14, 14]$ and $k=2$, then:

for $l=12$, $r=14$ the first condition fails because $12$ does not appear at least $k=2$ times.

for $l=13$, $r=14$ the first condition holds, because $13$ occurs at least $k=2$ times in $a$ and $14$ occurs at least $k=2$ times in $a$.

for $l=11$, $r=11$ the first condition holds, because $11$ occurs at least $k=2$ times in $a$.

A pair of $l$ and $r$ for which the first condition holds and $r-l$ is maximal is $l = 13$, $r = 14$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \leq k \leq n$) — the length of the array $a$ and the minimum amount of times each number in the range $[l, r]$ should appear respectively.

Then a single line follows, containing $n$ integers describing the array $a$ ($1 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case output $2$ numbers, $l$ and $r$ that satisfy the conditions, or "-1" if no numbers satisfy the conditions.

If multiple answers exist, you can output any.


-----Examples-----

Input
4
7 2
11 11 12 13 13 14 14
5 1
6 3 5 2 1
6 4
4 3 4 3 3 4
14 2
1 1 2 2 2 3 3 3 3 4 4 4 4 4
Output
13 14
1 3
-1
1 4


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms

Data structures


Solutions:
from collections import Counter

def main():
	for test in range(int(input())):
		s = input().split()
		k = int(s[1])
		a = sorted(map(int, input().split()))
		counter = Counter(a)
		(l, r, target_l, my_max) = (-1, -1, -1, -1)
		for val in counter:
			if counter[val] < k:
				continue
			if val == r + 1:
				r = val
				if val - l > my_max:
					(my_max, target_l) = (val - l, l)
			else:
				(l, r) = (val, val)
				if my_max == -1:
					(my_max, target_l) = (0, l)
		if my_max != -1:
			print('{} {}'.format(target_l, target_l + my_max))
		else:
			print(-1)
main()


def di():
	return map(int, input().split())

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

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

def si():
	return list(map(int, input()))
import sys

def check(nums, k):
	numbers = nums.split()
	numbers.sort(key=int)
	numbersktimes = []
	counter = 1
	prev = 'a'
	for i in numbers:
		if prev == i:
			counter += 1
		else:
			counter = 1
		if counter == k:
			numbersktimes.append(int(i))
		prev = i
	if len(numbersktimes) == 0:
		print(-1)
	else:
		longestFirst = numbersktimes[0]
		longestLast = numbersktimes[0]
		prev = numbersktimes[0]
		start = numbersktimes[0]
		for index in range(1, len(numbersktimes)):
			elem = numbersktimes[index]
			if elem == prev + 1:
				if elem - start > longestLast - longestFirst:
					longestLast = elem
					longestFirst = start
			else:
				start = elem
			prev = elem
		print(longestFirst, longestLast)

def main():
	numTestcases = int(sys.stdin.readline())
	for line in range(numTestcases):
		lengthandtimes = sys.stdin.readline()
		lt = lengthandtimes.split()
		check(sys.stdin.readline(), int(lt[1]))
main()


import sys

def check(nums, k):
	numbers = nums.split()
	numbers.sort(key=int)
	numbersktimes = []
	counter = 1
	prev = 'a'
	for i in numbers:
		if prev == i:
			counter += 1
		else:
			counter = 1
		if counter == k:
			numbersktimes.append(int(i))
		prev = i
	if len(numbersktimes) == 0:
		print(-1)
	else:
		longestFirst = numbersktimes[0]
		longestLast = numbersktimes[0]
		prev = numbersktimes[0]
		start = numbersktimes[0]
		for index in range(1, len(numbersktimes)):
			elem = numbersktimes[index]
			if elem == prev + 1:
				if elem - start > longestLast - longestFirst:
					longestLast = elem
					longestFirst = start
			else:
				start = elem
			prev = elem
		print(longestFirst, longestLast)

def main():
	numTestcases = int(sys.stdin.readline())
	for line in range(numTestcases):
		lengthandtimes = sys.stdin.readline()
		lt = lengthandtimes.split()
		check(sys.stdin.readline(), int(lt[1]))
main()


from collections import Counter
t = int(input())
for w in range(t):
	(n, k) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	c = Counter(arr)
	arr = sorted((z for (z, v) in c.items() if v >= k))
	if len(arr) == 0:
		print('-1')
		continue
	l = arr[0]
	r = arr[0]
	ansL = l
	ansR = r
	for val in arr:
		if val - r == 1:
			r = val
		else:
			if r - l > ansR - ansL:
				ansL = l
				ansR = r
			l = val
			r = val
	if r - l > ansR - ansL:
		ansL = l
		ansR = r
	print(ansL, ansR)


import sys

def check(nums, k):
	numbers = [int(x) for x in nums]
	numbers.sort()
	numbersktimes = []
	counter = 1
	prev = 'a'
	for i in numbers:
		if prev == i:
			counter += 1
		else:
			counter = 1
		if counter == k:
			numbersktimes.append(int(i))
		prev = i
	if len(numbersktimes) == 0:
		print(-1)
	else:
		longestFirst = numbersktimes[0]
		longestLast = numbersktimes[0]
		prev = numbersktimes[0]
		start = numbersktimes[0]
		for index in range(1, len(numbersktimes)):
			elem = numbersktimes[index]
			if elem == prev + 1:
				if elem - start > longestLast - longestFirst:
					longestLast = elem
					longestFirst = start
			else:
				start = elem
			prev = elem
		print(longestFirst, longestLast)

def main():
	numTestcases = int(input())
	for _ in range(numTestcases):
		(n, k) = [int(x) for x in input().strip().split()]
		check(input().strip().split(), k)
main()


t = int(input())
for nabor in range(t):
	(n, k) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	(f, count, pred) = (-1, 0, -1)
	a = b = -1
	maxrazn = 0
	last = None
	for (i, el) in enumerate(arr):
		if f < el:
			(f, count) = (el, 1)
		else:
			count += 1
		if count == k:
			if el != pred + 1:
				a = b = el
			else:
				b = el
			razn = b - a
			if razn > maxrazn:
				maxrazn = razn
			if razn == maxrazn:
				last = (a, b)
			pred = el
	if last is None:
		print(-1)
	else:
		print(last[0], last[1])


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	count = Counter(a)
	arr = [x for (x, y) in count.items() if y >= k]
	if len(arr) == 0:
		print(-1)
		continue
	arr.sort()
	mx = 0
	lans = arr[0]
	rans = arr[0]
	l = arr[0]
	for i in range(1, len(arr)):
		if arr[i] - arr[i - 1] == 1:
			if arr[i] - l > mx:
				lans = l
				rans = arr[i]
				mx = arr[i] - l
		else:
			l = arr[i]
	print(lans, rans)


from collections import Counter

def findRange(n, k, array):
	array.sort()
	cntr = Counter(array)
	array2 = []
	for key in cntr:
		if cntr[key] >= k:
			array2.append(key)
	n = len(array2)
	if n == 0:
		return (-1, -1)
	array2.sort()
	l = array2[0]
	r = array2[0]
	lt = array2[0]
	maxi = 0
	for i in range(1, n):
		if array2[i - 1] + 1 == array2[i]:
			if array2[i] - lt > maxi:
				l = lt
				r = array2[i]
				maxi = r - l
		else:
			lt = array2[i]
	return (l, r)

def main():
	tc = int(input())
	for _ in range(tc):
		(n, k) = map(int, input().split())
		array = [int(a) for a in input().split()]
		(l, r) = findRange(n, k, array)
		if l == -1:
			print(l)
		else:
			print(l, r)
main()


from collections import Counter
for case in range(int(input())):
	(nn, k) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	d = Counter(arr)
	arr = sorted((n for (n, v) in d.items() if v >= k))
	left = right = currLeft = currRight = -1
	for n in arr:
		if n - 1 == currRight:
			currRight += 1
		else:
			if currRight - currLeft >= right - left:
				(left, right) = (currLeft, currRight)
			currLeft = currRight = n
	if currRight - currLeft >= right - left:
		(left, right) = (currLeft, currRight)
	if left == -1:
		print(-1)
	else:
		print(left, right)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	cnt = {}
	for x in a:
		if x not in cnt:
			cnt[x] = 1
		else:
			cnt[x] += 1
	a = []
	for (x, r) in cnt.items():
		if r >= k:
			a.append(x)
	n = len(a)
	if n == 0:
		print(-1)
		return
	best = 0
	(a1, a2) = (-1, -1)
	l = 0
	succ = 1
	for i in range(1, n):
		if a[i - 1] + 1 == a[i]:
			succ += 1
		else:
			if i - l > best:
				best = i - l
				(a1, a2) = (l, i - 1)
			succ = 1
			l = i
	if n - l > best:
		(a1, a2) = (l, n - 1)
	print(a[a1], a[a2])
tst = int(input())
for tt in range(tst):
	solve()


from collections import defaultdict
from typing import Optional, Tuple

def solve() -> Optional[Tuple[int, int]]:
	(_, k) = map(int, input().split())
	count = defaultdict(lambda : 0)
	keys = []
	for e in sorted(map(int, input().split())):
		count[e] += 1
		if count[e] == k:
			keys.append(e)
	if not keys:
		return
	rl = rr = start = last = keys[0]
	for e in keys[1:]:
		if e == last + 1:
			if e - start > rr - rl:
				rl = start
				rr = e
		else:
			start = e
		last = e
	return (rl, rr)
results = []
for _ in range(int(input())):
	result = solve()
	if result is None:
		results.append('-1')
	else:
		results.append(f'{result[0]} {result[1]}')
print('\n'.join(results))


from collections import Counter
kvs = int(input())
for case in range(kvs):
	(nn, harsha) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	c = Counter(arr)
	arr = sorted((z for (z, v) in c.items() if v >= harsha))
	left = right = currLeft = currRight = -1
	for z in arr:
		if z - 1 == currRight:
			currRight += 1
		else:
			if currRight - currLeft >= right - left:
				(left, right) = (currLeft, currRight)
			currLeft = currRight = z
	if currRight - currLeft >= right - left:
		(left, right) = (currLeft, currRight)
	if left == -1:
		print(-1)
	else:
		print(left, right)


from collections import Counter
t = int(input())
answers = []
for _ in range(t):
	(_, k) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	mp = Counter(arr)
	arr = [key for (key, val) in mp.items() if val >= k]
	if not arr:
		print('-1')
		continue
	arr.sort()
	(l, r) = (arr[0], arr[0])
	(ansL, ansR) = (l, r)
	for val in arr:
		if val - r == 1:
			r = val
		else:
			if r - l > ansR - ansL:
				(ansL, ansR) = (l, r)
			(l, r) = (val, val)
	if r - l > ansR - ansL:
		(ansL, ansR) = (l, r)
	print(ansL, ansR)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted([int(i) for i in input().split()])
	d = Counter(a)
	(l, r) = (-1, -1)
	(res1, res2) = (-1, -1)
	dif = -99
	for el in d:
		if d[el] >= k:
			if l == -1:
				l = el
				r = el
				continue
			if el == r + 1:
				r = el
				continue
			if r - l > dif:
				res1 = l
				res2 = r
				dif = r - l
			l = el
			r = el
		elif l != -1:
			if r - l > dif:
				dif = r - l
				res1 = l
				res2 = r
				r = -1
				l = -1
	if r - l > dif:
		res1 = l
		res2 = r
	if res1 != -1:
		print(res1, res2)
	else:
		print(-1)


from collections import Counter
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	h = Counter(a)
	ans = (-math.inf, 0, 0)
	left = 0
	for right in range(n):
		if h[a[right]] < k:
			left = right + 1
			continue
		if right != 0 and a[right] - a[right - 1] > 1 and (right != left):
			left = right
			continue
		if a[right] - a[left] > ans[0]:
			ans = (a[right] - a[left], a[left], a[right])
	if ans[1] == ans[2] == 0:
		print(-1)
	else:
		print(str(ans[1]) + ' ' + str(ans[2]))


import sys
import bisect

def solve():
	inp = sys.stdin.readline
	(n, k) = map(int, inp().split())
	a = list(map(int, inp().split()))
	a.sort()
	d = dict()
	for i in a:
		d[i] = d.get(i, 0) + 1
	last = 0
	s = None
	p = None
	ans = (0, -1, -1)
	for i in a:
		if i == last:
			continue
		last = i
		if d[i] >= k:
			if p is not None and p == i - 1:
				p = i
				ans = max(ans, (p - s + 1, s, p))
			else:
				ans = max(ans, (1, i, i))
				s = i
				p = i
		else:
			s = None
			p = None
	if ans[0] == 0:
		print(-1)
	else:
		print(ans[1], ans[2])

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def task(n, k, a):
	a.sort()
	table = dict()
	for i in range(n):
		if not a[i] in table:
			table[a[i]] = 0
		table[a[i]] += 1
	lastkey = -100
	best = -1
	bestl = -1
	bestr = -1
	l = -1
	r = -1
	for key in table.keys():
		if key - lastkey > 1:
			l = -1
			r = -1
		if table[key] >= k:
			if l == -1:
				l = key
				r = key
			else:
				r = key
			if r - l > best:
				best = r - l
				bestl = l
				bestr = r
		else:
			l = -1
			r = -1
		lastkey = key
	if bestl == -1:
		print(-1)
		return
	print(bestl, bestr)
t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	task(n, k, a)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	cnt = {}
	tmp = []
	for e in arr:
		cnt[e] = cnt.get(e, 0) + 1
	for (_, v) in cnt.items():
		if v >= k:
			tmp.append(_)
	if not tmp:
		print(-1)
	else:
		l = r = ll = tmp[0]
		max_ = 0
		for i in range(1, len(tmp)):
			if tmp[i - 1] + 1 == tmp[i]:
				if tmp[i] - ll + 1 > max_:
					r = tmp[i]
					l = ll
					max_ = r - ll + 1
			else:
				ll = tmp[i]
		print(l, r)


import collections
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	c = collections.Counter(sorted(map(int, input().split())))
	d = collections.Counter()
	for (i, x) in c.items():
		if x >= k:
			d[i] = d[i - 1] + 1
	if not d:
		print(-1)
		continue
	(r, u) = d.most_common(1)[0]
	print(r - u + 1, r)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted([int(i) for i in input().split()])
	dic = Counter(a)
	(p, l) = ([], [])
	last_chance = None
	for el in dic:
		c = dic[el]
		if c >= k:
			last_chance = el
			if p == []:
				p = [el]
				continue
			if p[-1] == el - 1:
				p += [el]
				continue
			if len(p) >= 2:
				l += [(p[-1] - p[0], p[0], p[-1])]
			p = [el]
		else:
			if len(p) >= 2:
				l += [(p[-1] - p[0], p[0], p[-1])]
			p = []
	if len(p) >= 2:
		l += [(p[-1] - p[0], p[0], p[-1])]
	if l != []:
		l.sort()
		print(l[-1][1], l[-1][2])
	elif last_chance != None:
		print(last_chance, last_chance)
	else:
		print(-1)


import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = Counter(sorted(map(int, input().split())))
	w = [i for i in w if w[i] >= k]
	x = len(w)
	if x == 0:
		print(-1)
	elif x == 1:
		print(w[0], w[0])
	else:
		(c, d, s) = (0, -1, 0)
		for i in range(len(w) - 1):
			if w[i + 1] - w[i] == 1:
				c += 1
			else:
				if c > s:
					s = c
					d = i
				c = 0
		if c > s:
			s = c
			d = len(w) - 1
		print(w[d - s], w[d])


from collections import Counter
import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	dic = Counter(a)
	(res_left, res_right, l) = (0, 0, 0)
	for r in range(n):
		if dic[a[r]] < k:
			l = r + 1
			continue
		if r != 0 and a[r] - a[r - 1] > 1 and (l != r):
			l = r
			continue
		if a[r] - a[l] >= res_right - res_left:
			(res_left, res_right) = (a[l], a[r])
	if res_left == 0 and res_right == 0:
		print(-1)
	else:
		print(f'{res_left} {res_right}')


from collections import Counter
import sys
raw_input = sys.stdin.readlines

def solution():
	(n, k) = list(map(int, input().strip().split()))
	a = sorted(map(int, input().split()))
	(cnt, dp) = (Counter(a), Counter())
	result = 0
	for i in cnt:
		if cnt[i] >= k:
			dp[i] = dp[i - 1] + 1
		if dp[i] > dp[result]:
			result = i
	return '%s %s' % (result - dp[result] + 1, result) if result else -1
for case in range(int(input())):
	print('%s' % solution())


from collections import Counter
import math
from array import array
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = array('Q', sorted(map(int, input().split())))
	h = Counter(a)
	ans = (-math.inf, -1, -1)
	left = 0
	for right in range(n):
		if h[a[right]] < k:
			left = right + 1
			continue
		if right != 0 and a[right] - a[right - 1] > 1 and (right != left):
			left = right
			continue
		if a[right] - a[left] > ans[0]:
			ans = (a[right] - a[left], a[left], a[right])
	if ans[0] == -math.inf:
		print(-1)
	else:
		print(f'{ans[1]} {ans[2]}')


import collections
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	counter = collections.Counter(sorted(map(int, input().split())))
	strike = collections.Counter()
	for (a, t) in counter.items():
		if t >= k:
			strike[a] = strike[a - 1] + 1
	if not strike:
		print(-1)
		continue
	(r, d) = strike.most_common(1)[0]
	print(r - d + 1, r)


from collections import Counter
t = int(input())
for w in range(t):
	(n, k) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	mp = {}
	for a in arr:
		if a not in mp:
			mp[a] = 0
		mp[a] += 1
	arr = []
	for (_, key) in enumerate(mp):
		if mp[key] >= k:
			arr.append(key)
	arr.sort()
	if len(arr) == 0:
		print('-1')
		continue
	l = arr[0]
	r = arr[0]
	ansL = l
	ansR = r
	for val in arr:
		if val - r == 1:
			r = val
		else:
			if r - l > ansR - ansL:
				ansL = l
				ansR = r
			l = val
			r = val
	if r - l > ansR - ansL:
		ansL = l
		ansR = r
	print(ansL, ansR)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted([int(i) for i in input().split()])
	d = Counter(a)
	p = [-1, -1]
	res = [0, 0]
	dif = 0
	for el in d:
		if d[el] >= k:
			if el == p[1] + 1:
				p[1] = el
			else:
				ndif = p[-1] - p[0]
				if ndif > dif:
					res = p.copy()
					dif = ndif
				p = [el, el]
		else:
			ndif = p[-1] - p[0]
			if ndif > dif:
				res = p.copy()
				dif = ndif
	ndif = p[-1] - p[0]
	if ndif > dif:
		res = p.copy()
	if res[-1] != 0:
		print(*res, sep=' ')
	elif p[-1] != -1:
		print(*p, sep=' ')
	else:
		print(-1)


import sys
input = sys.stdin.readline
from collections import Counter
from random import randint
xx = randint(10 ** 5, 2 * 10 ** 5)
t = int(input())
for tests in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A = [a + xx for a in A]
	C = Counter(A)
	X = []
	for c in C:
		if C[c] >= k:
			X.append(c)
	if len(X) == 0:
		print(-1)
		continue
	X.sort()
	X.append(1 << 63)
	start = 1 << 63
	ANS = 0
	ANS2 = (-1, -1)
	for i in range(len(X)):
		if X[i] == X[i - 1] + 1:
			score += 1
		else:
			if start != 1 << 63:
				if score > ANS:
					ANS = score
					ANS2 = (X[i - 1] - score + 1, X[i - 1])
			start = X[i]
			score = 1
	print(*[a - xx for a in ANS2])


_ = int(input())
for __ in range(_):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr_sort = sorted(arr)
	arr_out = []
	tmp_arr = arr_sort[0]
	tmp_arr_count = 1
	for x in range(1, n):
		if arr_sort[x] == tmp_arr:
			tmp_arr_count += 1
		else:
			if tmp_arr_count >= k:
				arr_out.append(arr_sort[x - 1])
			tmp_arr_count = 1
			tmp_arr = arr_sort[x]
	if tmp_arr_count >= k:
		arr_out.append(arr_sort[-1])
	if not arr_out:
		print(-1)
		continue
	arr_out = sorted(arr_out)
	out = 1
	tmp_out = 1
	tmp = arr_out[0]
	beg = arr_out[0]
	end = arr_out[0]
	tmp_beg = arr_out[0]
	tmp_end = arr_out[0]
	for x in range(1, len(arr_out)):
		if arr_out[x] == tmp + 1:
			tmp_out += 1
			tmp_end = arr_out[x]
		else:
			if out < tmp_out:
				out = tmp_out
				beg = tmp_beg
				end = tmp_end
			tmp_beg = arr_out[x]
			tmp_end = arr_out[x]
			tmp_out = 1
		tmp = arr_out[x]
	if out < tmp_out:
		beg = tmp_beg
		end = tmp_end
	print(beg, end)


from collections import Counter as cnt
for p in range(int(input())):
	(n, k) = map(int, input().split())
	c = cnt(sorted(map(int, input().split())))
	d = cnt()
	for (i, x) in c.items():
		if x >= k:
			d[i] = d[i - 1] + 1
	if not d:
		print(-1)
		continue
	(r, u) = d.most_common(1)[0]
	print(r - u + 1, r)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a.sort()
	max_string = -1
	cur_string = -1
	lmax = -1
	rmax = -1
	counter = 0
	cur_val = a[0]
	cur_occurences = 0
	while counter < n:
		while counter < n and a[counter] == cur_val:
			cur_occurences += 1
			counter += 1
		if counter >= n:
			if cur_occurences >= k:
				cur_string += 1
			if cur_string > max_string:
				max_string = cur_string
				rmax = a[counter - 1]
				lmax = a[counter - 1] - max_string
		else:
			if cur_occurences >= k:
				cur_string += 1
				if cur_string > max_string:
					max_string = cur_string
					rmax = a[counter - 1]
					lmax = a[counter - 1] - max_string
				if a[counter] != cur_val + 1:
					cur_string = -1
			else:
				if cur_string > max_string:
					max_string = cur_string
					rmax = a[counter - 1]
					lmax = a[counter - 1] - max_string
				cur_string = -1
			cur_occurences = 0
			cur_val = a[counter]
	if max_string == -1:
		print(-1)
	else:
		print(lmax, rmax)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a = sorted(a)
	ct = Counter(a)
	l = 0
	r = 0
	b = []
	for (key, value) in ct.items():
		if value >= k:
			b.append(key)
	if len(b) > 0:
		l = 0
		ans = 0
		inter = 0
		li = b[0]
		for i in range(len(b) - 1):
			if b[i] + 1 == b[i + 1]:
				inter += 1
			else:
				ans = max(ans, inter)
				if ans == inter:
					l = li
				inter = 0
				li = b[i + 1]
		ans = max(ans, inter)
		if ans == inter:
			l = li
		if ans >= 0:
			print(l, l + ans)
		else:
			print(-1)
	else:
		print(-1)


def main():
	No_tests = int(input())
	for _ in range(No_tests):
		(l, r) = map(int, solve_one_test())
		if l == -1:
			print('-1')
		else:
			print(l, r)

def solve_one_test():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	freq_matrix = dict()
	for x in arr:
		if x not in freq_matrix:
			freq_matrix[x] = 0
		freq_matrix[x] += 1
	new_arr = list(freq_matrix.keys())
	l = 0
	r = len(new_arr) - 1
	answ = 0
	curr_atb = 0
	answ_l = -1
	answ_r = -1
	answ_delta = -1
	while l <= r:
		x = l
		curr_atb = 0
		did_something = False
		while x <= r and freq_matrix[new_arr[x]] >= k:
			did_something = True
			curr_atb += 1
			if x < r and new_arr[x] + 1 == new_arr[x + 1] and (freq_matrix[new_arr[x + 1]] >= k):
				x += 1
			else:
				break
		if curr_atb > answ or (did_something and curr_atb == answ and (x - l > answ_delta)):
			answ = curr_atb
			answ_l = new_arr[l]
			answ_r = new_arr[x]
			answ_delta = x - l
			curr_atb = 0
		l = x + 1
	return (answ_l, answ_r)
main()


import collections
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = list(map(int, input().split()))
	d.sort()
	p = collections.Counter(d)
	p1 = collections.Counter()
	mx = 0
	for i in p:
		if p[i] >= k:
			p1[i] = p1[i - 1] + 1
		if p1[i] > p1[mx]:
			mx = i
	if mx == 0:
		print(-1)
	else:
		print(mx - p1[mx] + 1, mx)


from collections import Counter

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	cnt = Counter(arr)
	ranges = []
	cur = []
	for (v, c) in cnt.items():
		if c >= k:
			if not cur or v == cur[-1] + 1:
				cur.append(v)
			else:
				ranges.append([*cur])
				cur = [v]
		else:
			if cur:
				ranges.append([*cur])
			cur.clear()
	if cur:
		ranges.append([*cur])
	if not ranges:
		print(-1)
		return
	best = max(ranges, key=lambda r: r[-1] - r[0])
	print(best[0], best[-1])
for t in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	count = {}
	for i in range(n):
		count[a[i]] = count.get(a[i], 0) + 1
	last = 0
	l = None
	r = None
	ans = (0, -1, -1)
	for i in a:
		if i == last:
			continue
		last = i
		if count[i] >= k:
			if l is not None and r == i - 1:
				r = i
				ans = max(ans, (r - l + 1, l, r))
			else:
				ans = max(ans, (1, i, i))
				l = i
				r = i
		else:
			l = None
			r = None
	if ans[0] == 0:
		print(-1)
	else:
		print(ans[1], ans[2])


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	lst = []
	for i in range(0, n):
		if len(lst) > 0 and lst[len(lst) - 1] == a[i]:
			continue
		if i + k - 1 < n and a[i + k - 1] == a[i]:
			lst.append(a[i])
	d = 1
	mx = 1
	if len(lst) == 0:
		print(-1)
		continue
	lst.sort()
	l = lst[0]
	r = l
	for i in range(1, len(lst)):
		if lst[i] - lst[i - 1] == 1:
			d += 1
		else:
			if mx < d:
				mx = d
				r = lst[i - 1]
				l = lst[i - d]
			d = 1
	if mx < d:
		mx = d
		r = lst[len(lst) - 1]
		l = lst[len(lst) - d]
	print(l, end=' ')
	print(r)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ll = list(map(int, input().split()))
	ll.sort()
	l = 0
	c = 0
	ans = [-1, -1]
	for i in range(n):
		if i == 0:
			l = ll[i]
			c = 1
		else:
			if ll[i] == ll[i - 1]:
				c += 1
			if ll[i] >= ll[i - 1] + 1:
				if c < k or ll[i] > ll[i - 1] + 1:
					l = ll[i]
				c = 1
		if c >= k:
			if ans[1] - ans[0] <= ll[i] - l:
				(ans[1], ans[0]) = (ll[i], l)
	if ans == [-1, -1]:
		print(-1)
	else:
		print(*ans)


from collections import Counter
x = lambda : map(int, input().split())
(t,) = x()
for _ in [1] * t:
	(n, k) = x()
	c = Counter(sorted(x()))
	d = Counter()
	m = 0
	for r in c:
		if c[r] >= k:
			d[r] = d[r - 1] + 1
		if d[r] > d[m]:
			m = r
	print(*[(m - d[m] + 1, m), (-1,)][m == 0])


from collections import Counter
for r in [0] * int(input()):
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	c = Counter(a)
	d = Counter()
	m = 0
	for i in c:
		if c[i] >= k:
			d[i] = d[i - 1] + 1
		if d[i] > d[m]:
			m = i
	if m == 0:
		print(-1)
		continue
	print(m - d[m] + 1, m)


import copy
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	d = {}
	for i in range(n):
		d[l[i]] = d.get(l[i], 0) + 1
	nl = []
	for i in d:
		if d[i] >= k:
			nl.append(i)
	if len(nl) == 0:
		print(-1)
		continue
	cur = [nl[0]]
	mx = [nl[0]]
	for i in range(1, len(nl)):
		if nl[i] == cur[-1] + 1:
			cur.append(nl[i])
		else:
			if len(cur) > len(mx):
				mx = cur.copy()
			cur = [nl[i]]
	if len(cur) > len(mx):
		mx = cur.copy()
	print(mx[0], mx[-1])


from collections import Counter
from random import shuffle
t = int(input())
for _ in range(t):
	(_, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	shuffle(arr)
	mp = Counter(arr)
	arr = []
	for key in mp.keys():
		if mp[key] >= k:
			arr.append(key)
	if not arr:
		print('-1')
		continue
	arr.sort()
	(l, r) = (arr[0], arr[0])
	(ansL, ansR) = (l, r)
	for val in arr:
		if val - r == 1:
			r = val
		else:
			if r - l > ansR - ansL:
				(ansL, ansR) = (l, r)
			(l, r) = (val, val)
	if r - l > ansR - ansL:
		(ansL, ansR) = (l, r)
	print(ansL, ansR)


from collections import defaultdict
import math
for cases in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	d = defaultdict(int)
	for i in l:
		d[i] += 1
	s = l
	front = s[0]
	rear = s[0]
	mx = -1
	l = -1
	r = -1
	for i in range(1, len(s)):
		if d[front] >= k and d[s[i]] >= k and (s[i] - s[i - 1] == 1 or s[i] - s[i - 1] == 0):
			rear = s[i]
		else:
			if mx < rear - front and d[front] >= k and (d[rear] >= k):
				mx = rear - front
				l = front
				r = rear
			front = s[i]
			rear = s[i]
	if rear - front > mx and d[front] >= k and (d[rear] >= k):
		l = front
		r = rear
	if l == -1:
		print(-1)
	else:
		print(l, r)


t = int(input())
answers = []
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	d = {}
	for n in a:
		if n not in d:
			d[n] = 1
		else:
			d[n] += 1
	invalid = []
	for key in d:
		if d[key] < k:
			invalid.append(key)
	for num in invalid:
		d.pop(num)
	valid = list(d.keys())
	valid.append(0)
	pairs = []
	l = valid[0]
	r = valid[0]
	for j in range(1, len(valid)):
		if abs(valid[j] - valid[j - 1]) > 1:
			pairs.append([l, r])
			l = valid[j]
		else:
			r = valid[j]
	max_lr = 0
	max_pair = -1
	for pair in pairs:
		diff = pair[1] - pair[0]
		if diff > max_lr:
			max_lr = diff
			max_pair = pair
	if max_pair != -1:
		answers.append([max_pair[0], max_pair[1]])
	elif len(valid) > 1:
		answers.append([valid[0], valid[0]])
	else:
		answers.append(-1)
for ans in answers:
	if ans == -1:
		print(ans)
	else:
		print(ans[0], ans[1])


from collections import Counter
from math import inf
from sys import stdin, stdout

def main():
	t = int(stdin.readline().strip())
	for _ in range(t):
		(n, k) = map(int, stdin.readline().split())
		arr = list(map(int, stdin.readline().split()))
		arr.sort()
		counts = []
		last = arr[0]
		c = 0
		for num in arr:
			if num == last:
				c += 1
			else:
				counts.append((last, c))
				last = num
				c = 1
		counts.append((last, c))
		(l, r) = (inf, -inf)
		i = 0
		j = 0
		while j < len(counts):
			while j < len(counts) and counts[j][1] >= k and (i == j or counts[j][0] == counts[j - 1][0] + 1):
				j += 1
			if i != j and counts[j - 1][0] - counts[i][0] > r - l:
				(l, r) = (counts[i][0], counts[j - 1][0])
			i = j
			while i < len(counts) and counts[i][1] < k:
				i += 1
			j = i
		if r < l:
			print(-1)
		else:
			print(l, r)
main()


t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	nums = dict()
	for num in arr:
		if num in nums:
			nums[num] += 1
		else:
			nums[num] = 1
	ans = 0
	cur = 0
	cur_l = 0
	cur_r = 0
	l = 0
	r = 0
	for num in nums:
		if nums[num] >= k:
			if num - 1 in nums and nums[num - 1] >= k:
				cur += 1
				cur_r += 1
			else:
				cur = 1
				cur_l = num
				cur_r = num
		if cur > ans:
			ans = cur
			l = cur_l
			r = cur_r
	if ans == 0:
		print(-1)
	else:
		print(l, r)


import sys
input = sys.stdin.readline
t = int(input())

def solution():
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	d = {}
	for n in a:
		if n not in d:
			d[n] = 1
		else:
			d[n] += 1
	impossible = []
	for key in d:
		if d[key] < k:
			impossible.append(key)
	for num in impossible:
		d.pop(num)
	works = list(d.keys()) + [0]
	possible = []
	(l, r) = (works[0], works[0])
	for j in range(1, len(works)):
		if abs(works[j] - works[j - 1]) > 1:
			possible.append([l, r])
			l = works[j]
		else:
			r = works[j]
	(max_lr, best_case) = (0, -1)
	for pair in possible:
		change = pair[1] - pair[0]
		if change > max_lr:
			max_lr = change
			best_case = pair
	if best_case != -1:
		return [best_case[0], best_case[1]]
	elif len(works) > 1:
		return [works[0], works[0]]
	else:
		return [-1]
res = []
for _ in range(t):
	tmp = solution()
	if len(tmp) == 1:
		print(tmp[0])
	else:
		print(tmp[0], tmp[1])


from math import ceil
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def mlt():
	return map(int, input().split())
mod = int(1000000000.0 + 7)

def initmap():
	return defaultdict(lambda : 0)

class Solution:

	def __init__(self) -> None:
		(x, y) = mlt()
		s = sorted([*mlt()])
		st = set(s)
		cnt = initmap()
		for n in s:
			cnt[n] += 1
		unix = list(st)
		isPossible = 0
		possibility = [0 for n in range(len(unix))]
		for n in range(len(unix)):
			if cnt[unix[n]] >= y:
				isPossible = 1
				possibility[n] = 1
		if not isPossible:
			print(-1)
			return
		s = []
		for n in range(len(unix)):
			if possibility[n]:
				s.append(unix[n])
		s.sort()
		mx = 1
		dp = [1 for n in range(len(s))]
		for n in range(1, len(s)):
			if s[n] == s[n - 1] + 1:
				dp[n] += dp[n - 1]
				mx = max(mx, dp[n])
		for n in range(len(s)):
			if dp[n] == mx:
				print(s[n] - dp[n] + 1, s[n])
				return
for _ in range(int(input())):
	Solution()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a = sorted(a)
	b = [[a[0], 1]]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			b[-1][1] += 1
		else:
			b.append([a[i], 1])
	l = 0
	r = 0
	max_d = 0
	max_l = 0
	max_r = 0
	while r < len(b):
		r += 1
		if b[r - 1][1] >= k and (r - l == 1 or b[r - 1][0] - b[r - 2][0] == 1):
			d = r - l
			if d > max_d:
				max_d = d
				max_l = b[l][0]
				max_r = b[r - 1][0]
		elif b[r - 1][1] >= k and r - l > 1:
			l = r - 1
		else:
			l = r
	if max_d == 0:
		print(-1)
	else:
		print(max_l, max_r)


from bisect import bisect_left
out = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	l = r = None
	i = j = 0
	best = 0
	ans = []
	while i < n - k + 1 and a[i] != a[i + k - 1]:
		i += 1
	if i > n - k:
		out.append([-1])
		continue
	while i < n - k + 1:
		l = a[i]
		r = a[i]
		j = i
		while j < n - k + 1 and a[j] == a[j + k - 1]:
			r += 1
			j = bisect_left(a, r)
			if j == n or a[j] != r:
				break
		r -= 1
		if r - l + 1 > best:
			best = r - l + 1
			ans = [l, r]
		i = j
		while i < n - k + 1 and a[i] != a[i + k - 1]:
			i += 1
	out.append(ans)
for i in out:
	print(*i)