每次测试时间限制：$3$ 秒
内存限制：$512$ 兆字节
题目描述 这是该问题的困难版本。唯一的不同是，在这个版本中，你需要为所有子中位数找到对应的子数组。

只有当问题的两个版本都解决后，你才能进行 hack。

一个整数 $v$ 是长度为 $m$ 的数组 $b$ 的中位数，当且仅当：

• $v$ 至少大于等于数组中的 $\lceil \frac{m}{2} \rceil$ 个元素，并且
• $v$ 至少小于等于数组中的 $\lceil \frac{m}{2} \rceil$ 个元素。

例如：

• $[9,3,7]$ 的唯一中位数是 $7$，
• $[5,3,7,9]$ 的中位数是 $5$、$6$ 和 $7$，
• $[2,2,2]$ 的唯一中位数是 $2$。

你被给定一个整数 $k$ 和一个数组 $a_1, \dots, a_n$，数组元素在 $1$ 到 $n$ 之间。

如果一个整数 $v$（$1 \le v \le n$）满足：存在至少一对下标 $(l,r)$ 使得

• $1 \le l \le r \le n$，
• $r - l + 1 \ge k$，
• $v$ 是子数组 $[a_l, \dots, a_r]$ 的一个中位数，

则称 $v$ 为子中位数。

请找出所有子中位数，并对每个子中位数给出任意一个对应的子数组下标 $(l,r)$。

输入
每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 50000$）——测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 300000$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
保证所有测试用例的 $n$ 之和不超过 $300000$。

输出
对于每个测试用例，按以下格式输出答案：

• 第一行输出一个整数 $c$，表示子中位数的个数。
• 接下来的 $c$ 行，每行输出三个整数 $v_i$、$l_i$、$r_i$，满足：
  • $r_i - l_i + 1 \ge k$，
  • $v_i$ 是子数组 $[a_{l_i}, \dots, a_{r_i}]$ 的一个中位数。

每个子中位数恰好报告一次，即 $v_1, \dots, v_c$ 必须互不相同。报告的顺序无关紧要。

如果有多个解，输出任意一个。

示例
输入

7
4 3
4 1 2 4
5 2
1 2 3 2 1
5 3
1 2 3 2 1
5 3
1 1 2 5 3
1 1
1
2 1
2 1
4 1
1 2 1 3

输出

3
2 1 4
3 1 4
4 1 4
3
1 4 5
2 1 5
3 3 4
1
2 2 4
3
1 1 3
2 2 4
3 3 5
1
1 1 1
2
1 1 2
2 1 2
3
1 1 1
2 2 2
3 4 4

注释
在第一个测试用例中，长度至少为 $k=3$ 的子数组有：

• $(l=1,r=3)$：$[4,1,2]$，唯一中位数是 $2$，
• $(l=2,r=4)$：$[1,2,4]$，唯一中位数是 $2$，
• $(l=1,r=4)$：$[4,1,2,4]$，中位数是 $2$、$3$ 和 $4$。

在第二个测试用例中，一个可能的输出是：

• $(l=4,r=5)$：$[2,1]$，中位数是 $1$ 和 $2$，
• $(l=1,r=5)$：唯一中位数是 $2$，
• $(l=3,r=4)$：$[3,2]$，中位数是 $2$ 和 $3$。

所有这些子数组的长度确实至少为 $2$。注意，可以证明没有长度至少为 $2$ 的子数组能使 $4$ 或 $5$ 成为中位数。