AT_agc022_b [AGC022B] GCD Sequence

[problemUrl]: https://atcoder.jp/contests/agc022/tasks/agc022_b ナガセは高校の優等生です。ある日のこと、ナガセは正の整数からなる特別な集合のとある性質を分析しています。 ナガセの考えでは、**異なる** 正の整数の集合 $ S\ =\ \{a_{1},\ a_{2},\ ...,\ a_{N}\} $ は、以下の条件を満たす場合に **特別** であると呼ばれます。条件：どの $ 1\ \leq\ i\ \leq\ N $ についても、$ a_{i} $ と、$ S $ のその他の要素の和の最大公約数は $ 1 $ **ではない**。 ナガセは、要素数 $ N $ の **特別** な集合を求めたいです。ところがこれは簡単すぎるので、難易度を上げることにしました。要素数 $ N $ の **特別** な集合であって、すべての要素の最大公約数が $ 1 $ であり、どの要素も $ 30000 $ 以下であるものを求めてみよ、とのことです。

入力は標準入力から以下の形式で与えられる。 > $ N $

$ S $ の要素を表す $ N $ 個の整数を空白で区切って出力せよ。$ S $ は以下の条件を満たさなければならない。 - 要素は $ 30000 $ 以下の **異なる** 正の整数でなければならない。 - $ S $ のすべての要素の最大公約数は $ 1 $ である。すなわち、$ S $ のすべての要素を割り切るような整数 $ d\ >\ 1 $ は存在しない。 - $ S $ は **特別** な集合である。 複数の解が存在する場合は、そのうちどれを出力してもよい。また、$ S $ の要素はどのような順番で出力してもよい。なお、与えられた制約の下で解が少なくとも一つ存在することが保証される。

### 制約 - $ 3\ \leq\ N\ \leq\ 20000 $ ### Sample Explanation 1 $ \{2,\ 5,\ 63\} $ は特別です。なぜなら、$ gcd(2,\ 5\ +\ 63)\ =\ 2,\ gcd(5,\ 2\ +\ 63)\ =\ 5,\ gcd(63,\ 2\ +\ 5)\ =\ 7 $ であり、さらに $ gcd(2,\ 5,\ 63)\ =\ 1 $ であるため、すべての判定条件を満たすからです。 なお、$ \{2,\ 4,\ 6\} $ は解として認められません。$ gcd(2,\ 4,\ 6)\ =\ 2\ >\ 1 $ であるからです。 ### Sample Explanation 2 $ \{2,\ 5,\ 20,\ 63\} $ は特別です。なぜなら、$ gcd(2,\ 5\ +\ 20\ +\ 63)\ =\ 2,\ gcd(5,\ 2\ +\ 20\ +\ 63)\ =\ 5,\ gcd(20,\ 2\ +\ 5\ +\ 63)\ =\ 10,\ gcd(63,\ 2\ +\ 5\ +\ 20)\ =\ 9 $ であり、さらに $ gcd(2,\ 5,\ 20,\ 63)\ =\ 1 $ であるため、すべての判定条件を満たすからです。