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.

For instance:

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)$$$.

Input

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$$$.

Output

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 reported exactly once, that is, integers $$$v_1, \ldots, v_c$$$ must be pairwise distinct. The order in which they are reported does not matter.

If there are many solutions, you can print any of them.

Note

In the first test case, the subarrays of length at least $$$k = 3$$$ are

$$$(l = 1, r = 3)$$$: $$$[4, 1, 2]$$$ whose only median is $$$2$$$,
$$$(l = 2, r = 4)$$$: $$$[1, 2, 4]$$$ whose only median is $$$2$$$, and
$$$(l = 1, r = 4)$$$: $$$[4, 1, 2, 4]$$$ whose medians are $$$2$$$, $$$3$$$, and $$$4$$$.

In the second test case, one possible output is

$$$(l = 4, r = 5)$$$: $$$[2, 1]$$$ whose medians are $$$1$$$ and $$$2$$$,
$$$(l = 1, r = 5)$$$: whose only median is $$$2$$$,
$$$(l = 3, r = 4)$$$: $$$[3, 2]$$$ whose medians are $$$2$$$ and $$$3$$$.

All of these subarrays are indeed of length at least $$$2$$$. Note that it can be proven that no subarray of length at least $$$2$$$ admits $$$4$$$ or $$$5$$$ as a median.

Idx	Name	Rating
A	Recycling Center	800
B	Deque Process	1100
C	Leftmost Below	1200
D	Sum of LDS	1600
E1	Submedians (Easy Version)	1900
E2	Submedians (Hard Version)	2600
F	Strict Triangle	3200

Codeforces Round 1039 (Div. 2)