У 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\). Найдите возможную последовательность действий для нее. Вам не нужно ничего минимизировать.
Выходные данные
Первая строка содержит целое неотрицательное число \(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}\).
Примечание
В первом наборе входных данных \(\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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 10 15
|
1
0 3 1 2 3
|
|
2
|
4
2 4 8 16
|
2
0 1 4
1 1 1
|