给定一个包含 $$$n$$$ 整数的数组 $$$a$$$,找到一系列值 $$$[x, y]$$$ ($$$x \le y$$$),并将 $$$a$$$ 精确地拆分为 $$$k$$$ ($$$1 \le k \le n$$$) 子数组,方法如下:
- 每个子数组由 $$$a$$$ 的几个连续元素组成,即对于某些 $$$l$$$ 和 $$$r$$$ 来说,它等于 $$$a_l, a_{l+1}, \ldots, a_r$$$ ($$$1 \leq l \leq r \leq n$$$)。
- $$$a$$$ 中的每个元素都属于一个子数组。
- 在每个子数组中,$$$[x, y]$$$(含)范围内的元素数量严格大于该范围之外的元素数量。当且仅当 $$$x \le a_i \le y$$$ 时,索引为 $$$i$$$ 的元素位于 $$$[x, y]$$$ 范围内。
打印任何最小化 $$$y - x$$$ 的解决方案。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度以及分区中所需的子数组的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是数组的第 $$$i$$$ 元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,打印 $$$k+1$$$ 行。
在第一行中,打印 $$$x$$$ 和 $$$y$$$ — 找到的范围的限制。
然后打印 $$$k$$$ 行,第 $$$i$$$ 行应包含 $$$l_i$$$ 和 $$$r_i$$$ ($$$1\leq l_i \leq r_i \leq n$$$) — 第 $$$i$$$ 子数组的限制。
您可以按任意顺序打印子数组。
示例
输入 #1
3 2 1 1 2 4 2 1 2 2 2 11 3 5 5 5 1 5 5 1 5 5 5 1
输出 #1
1 2 1 2 2 2 1 3 4 4 5 5 1 1 2 2 3 11
注意
在第一个测试中,应该只有一个子数组,它必须等于整个数组。 $$$[1, 2]$$$范围内有$$$2$$$元素,外部有$$$0$$$元素,如果选择的范围是$$$[1, 1]$$$,则内部($$$a_1$$$)内部存在$$$1$$$元素,外部($$$a_2$$$)内部存在$$$1$$$元素,则答案无效。
在第二个测试中,可以选择范围 $$$[2, 2]$$$,并将数组拆分为子数组 $$$(1, 3)$$$ 和 $$$(4, 4)$$$,在子数组 $$$(1, 3)$$$ 范围内有 $$$2$$$ 元素($$$a_2$$$ 和$$$a_3$$$) 和 $$$1$$$ 元素在 ($$$a_1$$$) 之外,子数组 $$$(4, 4)$$$ 中只有 $$$1$$$ 元素 ($$$a_4$$$),并且它在范围内。
在第三个测试中,可以选择范围 $$$[5, 5]$$$,并将数组拆分为子数组 $$$(1, 4)$$$、$$$(5, 7)$$$ 和 $$$(8, 11)$$$,在子数组 $$$(1, 4)$$$ 范围内有 $$$3$$$ 元素,并且$$$1$$$ 元素在外面,子数组 $$$(5, 7)$$$ 里面有 $$$2$$$ 元素,外面有 $$$1$$$ 元素,子数组 $$$(8, 11)$$$ 里面有 $$$3$$$ 元素,外面有 $$$1$$$ 元素。