CF1687E.Become Big For Me

Come, let's build a world where even the weak are not forgotten!

—Kijin Seija, Double Dealing Characters

Shinmyoumaru has a mallet that can turn objects bigger or smaller. She is testing it out on a sequence $a$ and a number $v$ whose initial value is $1$. She wants to make $v = \gcd\limits_{i\ne j}{a_i\cdot a_j}$ by no more than $10^5$ operations ($\gcd\limits_{i\ne j}{a_i\cdot a_j}$ denotes the $\gcd$ of all products of two distinct elements of the sequence $a$).

In each operation, she picks a subsequence $b$ of $a$, and does one of the followings:

• Enlarge: $v = v \cdot \mathrm{lcm}(b)$
• Reduce: $v = \frac{v}{\mathrm{lcm}(b)}$

Note that she does not need to guarantee that $v$ is an integer, that is, $v$ does not need to be a multiple of $\mathrm{lcm}(b)$ when performing Reduce.

Moreover, she wants to guarantee that the total length of $b$ chosen over the operations does not exceed $10^6$. Fine a possible operation sequence for her. You don't need to minimize anything.

来吧，让我们构建一个连弱者都不会被遗忘的世界！

——琪露诺·赛娅，《双重契约》

神明丸拥有一把可以将物体变大或变小的木槌。她正在对一个序列 $a$ 和一个初始值为 $1$ 的数 $v$ 进行测试。她的目标是通过至多 $10^5$ 次操作，使得 $v = \gcd\limits_{i\ne j}{a_i\cdot a_j}$（此处 $\gcd\limits_{i\ne j}{a_i\cdot a_j}$ 表示序列 $a$ 中所有互异下标元素两两乘积的最大公约数）。

每次操作中，她从 $a$ 中选取一个子序列 $b$，并执行以下两种操作之一：

• 放大：$v = v \cdot \mathrm{lcm}(b)$
• 缩小：$v = \frac{v}{\mathrm{lcm}(b)}$

注意：她无需保证 $v$ 始终为整数，即在执行“缩小”操作时，$v$ 不必是 $\mathrm{lcm}(b)$ 的倍数。

此外，她希望确保所有操作中所选子序列 $b$ 的总长度（即所有 $|b|$ 之和）不超过 $10^6$。请为她构造一个可行的操作序列。你无需最小化任何量。

The first line contains a single integer $n$ ($2\leq n\leq 10^5$) — the size of sequence $a$.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ($1\leq a_i\leq 10^6$) — the sequence $a$.

It can be shown that the answer exists.

第一行包含一个整数 $n$（$2\leq n\leq 10^5$）——序列 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1\leq a_i\leq 10^6$）——序列 $a$。

可以证明答案一定存在。

The first line contains a non-negative integer $k$ ($0\leq k\leq 10^5$) — the number of operations.

The following $k$ lines contains several integers. For each line, the first two integers $f$ ($f\in{0,1}$) and $p$ ($1\le p\le n$) stand for the option you choose ($0$ for Enlarge and $1$ for Reduce) and the length of $b$. The other $p$ integers of the line $i_1,i_2,\ldots,i_p$ ($1\le i_1 \lt i_2 \lt \ldots \lt i_p\le n$) represents the indexes of the subsequence. Formally, $b_j=a_{i_j}$.

第一行包含一个非负整数 $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 \lt i_2 \lt \ldots \lt i_p\le n$）表示子序列的下标。形式化地，有 $b_j=a_{i_j}$。

Test case 1:

$\gcd\limits_{i\ne j}{a_i\cdot a_j}=\gcd{60,90,150}=30$.

Perform $v = v\cdot \operatorname{lcm}{a_1,a_2,a_3}=30$.

Test case 2:

$\gcd\limits_{i\ne j}{a_i\cdot a_j}=8$.

Perform $v = v\cdot \operatorname{lcm}{a_4}=16$.

Perform $v = \frac{v}{\operatorname{lcm}{a_1}}=8$.

测试用例 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$。

测试用例 2：

$\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$。