题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，任务是找到任意两个数字 $l$ 和 $r(l≤r)$，使得：

• 对于每个 $x(l≤x≤r)$，至少出现 $k$ 次（即 $k$ 个或更多个数组元素等于 $x$）。
• $r−l$ 值最大化。

如果没有数字满足条件，则输出 $-1$。

例如，如果 $a=[11,11,12,13,13,14,14]$ 且 $k=2$，则：

对于 $l＝12，r＝14$，第一个条件不成立，因为 $12$ 没有出现至少 $k＝2$ 次。

对于 $l＝13，r＝14$，第一个条件成立，因为 $13$ 在 $a$ 中出现 $k＝2$ 次，而 $14$ 在 $a$ 中出现 $k＝2$ 次。

对于 $l＝11，r＝11$，第一个条件成立，因为 $11$ 在 $a$ 中出现 $k＝2$ 次。

第一个条件成立且 $r−l$ 最大的一对 $l$ 和 $r$ 为 $l=13，r=14$。

输入格式

输入的第一行包含单个整数 $t(1≤t≤1000)$ 表示测试用例的数量。测试用例描述如下。

每个测试用例的第一行包含整数 $n$ 和 $k(1≤n≤2\times 10^5，1≤k≤n)$ 表示数组 $a$ 的长度和 $[l,r]$ 范围内每个数字的最少出现次数。

接下来是一行，包含 $n$ 个整数，描述数组 $a(1≤a_i≤10^9)$。

保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每个测试用例，输出满足条件的 $2$ 个数字，$l$ 和 $r$，如果没有数字满足条件，则输出 -1。

如果存在多个答案，则可以输出任意满足题目要求的答案。

测试样例

5
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
6 1
2 3 4 7 8 9

13 14
1 3
-1
1 4
7 9

样例说明

最后一个样例中，区间 $[2,4]$ 和区间 $[7,9]$ 都是最长区间，输出任何一个都可以。