E2. Подмедианы (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие заключается в том, что в этой версии вам нужно найти подмассив для всех подмедиан.

Вы можете делать взломы только в том случае, если обе версии задачи решены.

Целое число $$$v$$$ является медианой массива $$$b$$$ длины $$$m$$$ тогда и только тогда, когда:

  • $$$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, \ldots, a_n$$$ целых чисел от $$$1$$$ до $$$n$$$.

Целое число $$$v$$$ от $$$1$$$ до $$$n$$$ называется подмедианой, если существует хотя бы одна пара индексов $$$(l, r)$$$ такая, что

  • $$$1 \leq l \leq r \leq n$$$,
  • $$$r - l + 1 \geq k$$$,
  • $$$v$$$ является медианой подмассива $$$[a_l, \ldots, a_r]$$$.

Найдите все подмедианы и для каждой из них найдите любую соответствующую пару индексов $$$(l, r)$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого теста содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 300\,000$$$).

Вторая строка каждого теста содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$300\,000$$$.

Выходные данные

Для каждого теста выведите ваш ответ в следующем формате.

В первой строке выведите $$$c$$$, количество подмедиан.

На $$$i$$$-й из следующих $$$c$$$ строк выведите три целых числа $$$v_i$$$, $$$l_i$$$ и $$$r_i$$$ такие, что

  • $$$r_i - l_i + 1 \geq k$$$, и
  • $$$v_i$$$ является одной из медиан подмассива $$$[a_{l_i}, \ldots, a_{r_i}]$$$.

Каждая подмедиана должна быть указана ровно один раз, то есть целые числа $$$v_1, \ldots, 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$$$ в качестве медианы.