This is the hard version of the problem. The only difference is that in this version, you are asked to find a subarray for all submedians . You can make hacks only if both versions of the problem are solved. An integer (v) is a median of an array (b) of length (m) if and only if: (v) is greater than or equal to at least (\lceil \frac{m}{2} \rceil) elements of the array, and (v) is less than or equal to at least (\lceil \frac{m}{2} \rceil) elements of the array. the only median of (9, 3, 7) is (7), the medians of (5, 3, 7, 9) are (5), (6), and (7), and the only median of (2, 2, 2) is (2). You're given an integer (k) and an array (a_1, \ldots, a_n) of integers between (1) and (n). An integer (v) from (1) to (n) is said to be a submedian if there exists at least one pair of indices ((l, r)) such that (1 \leq l \leq r \leq n), (r - l + 1 \geq k), (v) is a median of the subarray (a_l, \ldots, a_r). Find all submedians and for each of them, find any corresponding pair of indices ((l, r)). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 50\,000)). The description of the test cases follows. The first line of each test case contains two integers (n) and (k) ((1 \leq k \leq n \leq 300\,000)). The second line of each test case contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \leq a_i \leq n)). It is guaranteed that the sum of (n) over all test cases doesn't exceed (300\,000). For each test case, output your answer in the following format. On the first line, output (c), the number of submedians . On the (i)-th of the following (c) lines, output three integers (v_i), (l_i), and (r_i) such that (r_i - l_i + 1 \geq k), and (v_i) is one of the medians of the subarray (a_{l_i}, \ldots, a_{r_i}). Each submedian should be