E. Стань больше
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Shinmyoumaru есть молоток, который может увеличивать или уменьшать предметы. Она проверяет это на последовательности $$$a$$$ и числе $$$v$$$, начальное значение которого равно $$$1$$$. Она хочет получить $$$v = \gcd\limits_{i\ne j}\{a_i\cdot a_j\}$$$, используя не более $$$10^5$$$ операций ($$$\gcd\limits_{i\ne j}\{a_i\cdot a_j\}$$$обозначает $$$\gcd$$$ всех произведений двух различных элементов последовательности $$$a$$$).

В каждой операции она выбирает подпоследовательность $$$b$$$ последовательности $$$a$$$ и выполняет одно из следующих действий.

  • Увеличить: $$$v = v \cdot \mathrm{lcm}(b)$$$
  • Уменьшить: $$$v = \frac{v}{\mathrm{lcm}(b)}$$$

Обратите внимание, что ей не нужно гарантировать, чтобы $$$v$$$ являлось целым числом, то есть $$$v$$$ не обязательно должно быть кратным $$$\mathrm{lcm}(b)$$$ при выполнении операции уменьшать.

Кроме того, она хочет гарантировать, чтобы суммарная длина $$$b$$$, выбранных для операций, не превышала $$$10^6$$$. Найдите возможную последовательность действий для нее. Вам не нужно ничего минимизировать.

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

Первая строка содержит единственное целое число $$$n$$$ ($$$2\leq n\leq 10^5$$$) — размер последовательности $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\cdots,a_n$$$ ($$$1\leq a_i\leq 10^6$$$) — последовательность $$$a$$$.

Можно показать, что ответ существует.

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

Первая строка содержит целое неотрицательное число $$$k$$$ ($$$0\leq k\leq 10^5$$$) — количество операций.

Следующие $$$k$$$ строк содержат несколько целых чисел. В каждой строке первые два целых числа $$$f$$$ ($$$f\in\{0,1\}$$$) и $$$p$$$ ($$$1\le p\le n$$$) обозначают выбранный вами вариант ($$$0$$$ для увеличения и $$$1$$$ для уменьшения) и длину $$$b$$$. Остальные целые числа $$$p$$$ в строке $$$i_1,i_2,\ldots,i_p$$$ ($$$1\le i_1<i_2<\ldots<i_p\le n$$$) представляют собой индексы подпоследовательности. Формально $$$b_j=a_{i_j}$$$.

Примеры
Входные данные
3
6 10 15
Выходные данные
1
0 3 1 2 3
Входные данные
4
2 4 8 16
Выходные данные
2
0 1 4
1 1 1
Примечание

В первом наборе входных данных $$$\gcd\limits_{i\ne j}\{a_i\cdot a_j\}=\gcd\{60,90,150\}=30$$$.

Выполните $$$v = v\cdot \operatorname{lcm}\{a_1,a_2,a_3\}=30$$$.

Во втором наборе входных данных $$$\gcd\limits_{i\ne j}\{a_i\cdot a_j\}=8$$$.

Выполните $$$v = v\cdot \operatorname{lcm}\{a_4\}=16$$$.

Затем выполните $$$v = \frac{v}{\operatorname{lcm}\{a_1\}}=8$$$.