Вчера в бакалее супермаркета была ярмарка. На ярмарке было выставлено в ряд n баночек с приправами, баночки были пронумерованы числами от 1 до n слева направо. После мероприятия баночки перемешались и бакалейщику требуется упорядочить их в порядке возрастания номеров.
Бакалейщик имеет в распоряжении аппарат, который может взять 5 (или меньше) баночек, и переставить их между собой так, как захочет бакалейщик. При этом баночки не обязательно должны стоять подряд. Например из порядка баночек 2, 6, 5, 4, 3, 1 можно получить порядок 1, 2, 3, 4, 5, 6, если выбрать баночки на позициях 1, 2, 3, 5 и 6.
Какое наименьшее количество таких операций потребуется, чтобы упорядочить все баночки в порядке возрастания номеров?
Выходные данные
В первой строке выведите наименьшее количество операций для того, чтобы упорядочить все баночки в порядке возрастания номеров. Далее выведите описание всех действий в следующем формате.
В первой строке описания одного действия укажите сколько баночек нужно взять (k), во второй строке — баночки на каких позициях выбрать (b1, b2, ..., bk), в третьей — новый порядок баночек (c1, c2, ..., ck). После выполнения операции баночка с позиции bi будет стоять на позиции ci. Набор (c1, c2, ..., ck) должен являться перестановкой набора (b1, b2, ..., bk).
Если решений несколько, выведите любое.
Примечание
Рассмотрим первый пример. Баночки можно упорядочить за две операции.
Во время перво операции мы возьмем баночки на позициях 1, 3, 6 и 4 и поставим их таким образом, что баночка, которая была на позиции 1 будет после завершения операции находиться на позиции 3, баночка с позиции 3 окажется на позиции 6, баночка с позиции 6 будет находиться на позиции 4, а баночка с позиции 4 переместится на позицию 1.
После первой операции порядок будет выглядеть так: 1, 5, 3, 4, 2, 6.
Во время второй операции баночки на позициях 2 и 5 поменяются местами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 5 6 1 2 4
|
2
4
1 3 6 4
3 6 4 1
2
2 5
5 2
|
|
2
|
14
9 13 11 3 10 7 12 14 1 5 4 6 8 2
|
3
4
2 13 8 14
13 8 14 2
5
6 7 12 5 10
7 12 6 10 5
5
3 11 4 1 9
11 4 3 9 1
|