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 $ opreations ( $ \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.

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.

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

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