Given an array $a$ of $n$ integers, find a range of values $[x, y]$ ($x \le y$), and split $a$ into exactly $k$ ($1 \le k \le n$) subarrays in such a way that:

Each subarray is formed by several continuous elements of $a$, that is, it is equal to $a_l, a_{l+1}, \ldots, a_r$ for some $l$ and $r$ ($1 \leq l \leq r \leq n$).

Each element from $a$ belongs to exactly one subarray.

In each subarray the number of elements inside the range $[x, y]$ (inclusive) is strictly greater than the number of elements outside the range. An element with index $i$ is inside the range $[x, y]$ if and only if $x \le a_i \le y$.

Print any solution that minimizes $y - x$.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 3 \cdot 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the array $a$ and the number of subarrays required in the partition.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) where $a_i$ is the $i$-th element of the array.

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


-----Output-----

For each test case, print $k+1$ lines.

In the first line, print $x$ and $y$ — the limits of the found range.

Then print $k$ lines, the $i$-th should contain $l_i$ and $r_i$ ($1\leq l_i \leq r_i \leq n$) — the limits of the $i$-th subarray.

You can print the subarrays in any order.


-----Examples-----

Input
3
2 1
1 2
4 2
1 2 2 2
11 3
5 5 5 1 5 5 1 5 5 5 1
Output
1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11


-----Note-----

In the first test, there should be only one subarray, which must be equal to the whole array. There are $2$ elements inside the range $[1, 2]$ and $0$ elements outside, if the chosen range is $[1, 1]$, there will be $1$ element inside ($a_1$) and $1$ element outside ($a_2$), and the answer will be invalid.

In the second test, it is possible to choose the range $[2, 2]$, and split the array in subarrays $(1, 3)$ and $(4, 4)$, in subarray $(1, 3)$ there are $2$ elements inside the range ($a_2$ and $a_3$) and $1$ element outside ($a_1$), in subarray $(4, 4)$ there is only $1$ element ($a_4$), and it is inside the range.

In the third test, it is possible to choose the range $[5, 5]$, and split the array in subarrays $(1, 4)$, $(5, 7)$ and $(8, 11)$, in the subarray $(1, 4)$ there are $3$ elements inside the range and $1$ element outside, in the subarray $(5, 7)$ there are $2$ elements inside and $1$ element outside and in the subarray $(8, 11)$ there are $3$ elements inside and $1$ element outside.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Sorting

Amortized analysis

Greedy algorithms

Data structures
Skill types: Data structures

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = a[:]
	b.sort()
	needed = (n + k + 1) // 2 - 1
	(md, ml, mr) = (b[needed] - b[0], 0, needed)
	for i in range(needed, n):
		cd = b[i] - b[i - needed]
		if cd < md:
			(md, ml, mr) = (cd, i - needed, i)
	print(b[ml], b[mr])
	balance = 0
	splits = []
	for i in range(n):
		if len(splits) >= k - 1:
			break
		if b[ml] <= a[i] <= b[mr]:
			balance += 1
		else:
			balance -= 1
		if balance > 0:
			balance = 0
			splits.append(i)
	if k > 1:
		print(1, splits[0] + 1)
		for i in range(1, k - 1):
			print(splits[i - 1] + 2, splits[i] + 1)
		print(splits[-1] + 2, n)
	else:
		print(1, n)


import math

def solve(a, n, k):
	m = math.ceil((n + k) / 2)
	cnt = [0] * (n + 1)
	for aa in a:
		cnt[aa] += 1
	min_len = n + 111
	(l, r) = (0, 0)
	(i, j) = (1, 1)
	num = 0
	while j <= n + 1:
		if num < m:
			if j == n + 1:
				break
			num += cnt[j]
			j += 1
		else:
			if j - i < min_len:
				min_len = j - i
				l = i
				r = j - 1
			num -= cnt[i]
			i += 1
	print(l, r)
	begin = 0
	for i in range(k - 1):
		num = 0
		for j in range(begin, n):
			if l <= a[j] <= r:
				num += 1
			else:
				num -= 1
			if num >= 1:
				print(begin + 1, j + 1)
				begin = j + 1
				break
	print(begin + 1, n)
	return
t = int(input())
while t:
	(n, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	solve(a, n, k)
	t -= 1


from collections import Counter

def solve_case():
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	stats = Counter(a)
	keys = sorted(stats.keys())
	min_sum = (n + k + 1) // 2
	(l, lv, s) = (0, keys[0], 0)
	(blv, brv, bdiff) = (0, 0, 10 ** 10)
	for (r, rv) in enumerate(keys):
		s += stats[rv]
		if s < min_sum:
			continue
		while s - stats[lv] >= min_sum:
			s -= stats[lv]
			l += 1
			lv = keys[l]
		diff = rv - lv
		if diff < bdiff:
			(bdiff, blv, brv) = (diff, lv, rv)
	print(blv, brv)
	last_idx = 0
	balance = 0
	found = 0
	for (idx, value) in enumerate(a):
		if found == k - 1:
			break
		balance += 1 if blv <= value <= brv else -1
		if balance > 0:
			print(last_idx + 1, idx + 1)
			(last_idx, balance) = (idx + 1, 0)
			found += 1
	print(last_idx + 1, n)
t = int(input())
for _ in range(t):
	solve_case()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sa = sorted(a)
	cnt = [0 for i in range(n + 1)]
	for i in range(n):
		cnt[a[i]] += 1
	for i in range(2, n + 1):
		cnt[i] += cnt[i - 1]
	ans = (-1, n)
	need = (n + k + 1) // 2
	for i in range(n - need + 1):
		new_ans = (sa[i], sa[i + need - 1])
		if new_ans[1] - new_ans[0] < ans[1] - ans[0]:
			ans = new_ans
	print(ans[0], ans[1])
	lst = 0
	cnt = 0
	for i in range(n):
		if k == 1:
			break
		if ans[0] <= a[i] <= ans[1]:
			cnt += 1
		else:
			cnt -= 1
		if cnt > 0:
			print(lst + 1, i + 1)
			lst = i + 1
			cnt = 0
			k -= 1
	print(lst + 1, n)


ans = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	(a, b) = (1, n)
	kol = (n + k + 1) // 2
	used = [0] * (n + 2)
	for i in range(n):
		used[x[i]] += 1
	(l, r) = (1, 1)
	m = 0
	for r in range(1, n + 1):
		m += used[r]
		while m - used[l] >= kol:
			m -= used[l]
			l += 1
		if m >= kol and r - l < b - a:
			(a, b) = (l, r)
	otv = []
	otv.append([a, b])
	l = 0
	k1 = 0
	k2 = 0
	for i in range(0, n):
		if k == 1:
			otv.append([i + 1, n])
			break
		if a <= x[i] <= b:
			k1 += 1
		else:
			k2 += 1
		if k1 > k2:
			otv.append([l + 1, i + 1])
			l = i + 1
			k -= 1
			(k1, k2) = (0, 0)
	ans.append(otv)
for i in range(len(ans)):
	for j in range(len(ans[i])):
		print(ans[i][j][0], ans[i][j][1])


import copy
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = copy.deepcopy(a)
	b.sort()
	(x, y) = (0, b[n - 1])
	ln = (n + k + 1) // 2
	for i in range(0, n - ln + 1):
		if y - x > b[i + ln - 1] - b[i]:
			(x, y) = (b[i], b[i + ln - 1])
	print(x, y)
	c = [1 if x <= a[i] <= y else -1 for i in range(n)]
	(rch, sum) = (1, 0)
	ls = 0
	for i in range(n):
		if rch == k:
			break
		sum += c[i]
		if sum == rch:
			print(ls + 1, i + 1)
			ls = i + 1
			rch += 1
	print(ls + 1, n)