Codeforces Round 796 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

constructive algorithms

greedy

math

number theory

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Become Big For Me

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputCome, 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.

Input

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.

Output

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<i_2<\ldots<i_p\le n$$$) represents the indexes of the subsequence. Formally, $$$b_j=a_{i_j}$$$.

Examples

Input

3 6 10 15

Output

1 0 3 1 2 3

Input

4 2 4 8 16

Output

2 0 1 4 1 1 1

Note

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$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/10/2023 14:14:10 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|