给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$,您的任务是找到任意两个数字 $$$l$$$ 和 $$$r$$$ ($$$l \leq r$$$),使得:
- 对于每个 $$$x$$$ $$$(l \leq x \leq r)$$$,$$$x$$$ 出现在 $$$a$$$ 中至少 $$$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 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — 数组 $$$a$$$ 的长度以及 $$$[l, r]$$$ 范围内每个数字应分别出现的最小次数。
接下来是一行,包含描述数组 $$$a$$$ 的 $$$n$$$ 整数 ($$$1 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出满足条件的 $$$2$$$ 数字、$$$l$$$ 和 $$$r$$$ ,如果没有数字满足条件,则输出“-1”。
如果存在多个答案,您可以输出任何答案。
示例
输入 #1
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
输出 #1
13 14 1 3 -1 1 4