Во внешней памяти нового поколения расположен массив целых чисел \(a[1 \ldots n] = [a_1, a_2, \ldots, a_n]\).
Данный вид памяти не позволяет изменить значение произвольного элемента по его индексу. Вместо этого можно вырезать любой подотрезок данного массива, циклически сдвинуть его на произвольную величину и вставить обратно на то же самое место.
Формально, один такий циклический сдвиг состоит из двух последовательных действий:
- Выбрать произвольные \(l\) и \(r\) (\(1 \le l < r \le n\)) — границы изменяемого подотрезка массива.
- Заменить подотрезок массива \(a[l \ldots r]\) на его циклический сдвиг влево на произвольную величину \(d\). Поясним понятие циклический сдвиг: последовательность \([1, 4, 1, 3]\) является циклическим сдвигом последовательности \([3, 1, 4, 1]\) на \(1\) влево. Последовательность \([4, 1, 3, 1]\) является циклическим сдвигом последовательности \([3, 1, 4, 1]\) на \(2\) влево.
Например, если \(a = [1, \color{blue}{3, 2, 8}, 5]\), то при выборе \(l = 2\), \(r = 4\) и \(d = 2\) получается подотрезок \(a[2 \ldots 4] = [3, 2, 8]\). Затем этот отрезок сдвигается на \(d = 2\) влево, и получается подотрезок \([8, 3, 2]\), который в итоге встает на место исходных элементов отрезка. Получается \(a = [1, \color{blue}{8, 3, 2}, 5]\).
Отсортируйте заданный массив \(a\), используя не более \(n\) циклических сдвигов любых его отрезков. Обратите внимание, что вам не нужно минимизировать количество циклических сдвигов. Подойдет любой способ, который требует \(n\) или менее циклических сдвигов.
Выходные данные
Выведите \(t\) ответов на все наборы входных данных.
Первая строка ответа на набор входных данных должна содержать число \(k\) (\(0 \le k \le n\)) — количество действий, которыми сортируется массив. Следующие \(k\) строк должны содержать описания действий в формате «\(l\) \(r\) \(d\)» (без кавычек), где \(l\) и \(r\) (\(1 \le l < r \le n\)) — это границы сдвигаемого отрезка, а \(d\) (\(1 \le d \le r - l\)) — величина сдвига. Напоминаем, что по условию задачи рассматриваются циклические сдвиги влево, и выбранный отрезок будет сдвинут на \(d\) влево.
Обратите внимание, что от вас не требуется найти минимальное необходимое для сортировки количество циклических сдвигов. Подойдет любой способ сортировки, количество сдвигов в котором не превосходит \(n\).
Если заданный массив \(a\) уже отсортирован, то одним из возможных ответов является \(k = 0\) и пустая последовательность циклических сдвигов.
Если возможных ответов несколько, выведите любой из них.