{"problem":{"name":"C. Marco and GCD Sequence","description":{"content":"In a dream Marco met an elderly man with a pair of black glasses. The man told him the key to immortality and then disappeared with the wind of time. When he woke up, he only remembered that the key ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF894C"},"statements":[{"statement_type":"Markdown","content":"In a dream Marco met an elderly man with a pair of black glasses. The man told him the key to immortality and then disappeared with the wind of time.\n\nWhen he woke up, he only remembered that the key was a sequence of positive integers of some length _n_, but forgot the exact sequence. Let the elements of the sequence be _a_1, _a_2, ..., _a__n_. He remembered that he calculated _gcd_(_a__i_, _a__i_ + 1, ..., _a__j_) for every 1 ≤ _i_ ≤ _j_ ≤ _n_ and put it into a set _S_. _gcd_ here means the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).\n\nNote that even if a number is put into the set _S_ twice or more, it only appears once in the set.\n\nNow Marco gives you the set _S_ and asks you to help him figure out the initial sequence. If there are many solutions, print any of them. It is also possible that there are no sequences that produce the set _S_, in this case print _\\-1_.\n\n## Input\n\nThe first line contains a single integer _m_ (1 ≤ _m_ ≤ 1000) — the size of the set _S_.\n\nThe second line contains _m_ integers _s_1, _s_2, ..., _s__m_ (1 ≤ _s__i_ ≤ 106) — the elements of the set _S_. It's guaranteed that the elements of the set are given in strictly increasing order, that means _s_1 < _s_2 < ... < _s__m_.\n\n## Output\n\nIf there is no solution, print a single line containing _\\-1_.\n\nOtherwise, in the first line print a single integer _n_ denoting the length of the sequence, _n_ should not exceed 4000.\n\nIn the second line print _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the sequence.\n\nWe can show that if a solution exists, then there is a solution with _n_ not exceeding 4000 and _a__i_ not exceeding 106.\n\nIf there are multiple solutions, print any of them.\n\n[samples]\n\n## Note\n\nIn the first example 2 = _gcd_(4, 6), the other elements from the set appear in the sequence, and we can show that there are no values different from 2, 4, 6 and 12 among _gcd_(_a__i_, _a__i_ + 1, ..., _a__j_) for every 1 ≤ _i_ ≤ _j_ ≤ _n_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在梦中，马可遇见了一位戴着黑色眼镜的老人。老人告诉他永生的关键，然后随着时光之风消失了。\n\n当他醒来时，只记得关键是一个长度为 $n$ 的正整数序列，但忘记了具体的序列。设序列的元素为 $a_1, a_2, ..., a_n$。他记得自己计算了每一个 $1 ≤ i ≤ j ≤ n$ 的 $gcd(a_i, a_{i+1}, ..., a_j)$，并将结果放入一个集合 $S$ 中。此处的 $gcd$ 表示最大公约数。\n\n注意，即使某个数字被多次加入集合 $S$，它在集合中也仅出现一次。\n\n现在马可给你集合 $S$，并要求你帮助他还原原始序列。如果有多种解，输出任意一种即可。也可能不存在能生成集合 $S$ 的序列，此时请输出 _-1_。\n\n第一行包含一个整数 $m$ ($1 ≤ m ≤ 1000$) —— 集合 $S$ 的大小。\n\n第二行包含 $m$ 个整数 $s_1, s_2, ..., s_m$ ($1 ≤ s_i ≤ 10^6$) —— 集合 $S$ 的元素。保证集合元素按严格递增顺序给出，即 $s_1 < s_2 < ... < s_m$。\n\n如果没有解，输出一行 _-1_。\n\n否则，第一行输出一个整数 $n$，表示序列的长度，$n$ 不应超过 $4000$。\n\n第二行输出 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^6$) —— 序列。\n\n我们可以证明，如果存在解，则一定存在一个满足 $n$ 不超过 $4000$ 且所有 $a_i$ 不超过 $10^6$ 的解。\n\n如果有多个解，输出任意一个即可。\n\n在第一个例子中，$2 = gcd(4, 6)$，集合中的其他元素出现在序列中，我们可以证明在所有 $1 ≤ i ≤ j ≤ n$ 的 $gcd(a_i, a_{i+1}, ..., a_j)$ 中，不存在除 $2$、$4$、$6$ 和 $12$ 以外的值。\n\n## Input\n\n第一行包含一个整数 $m$ ($1 ≤ m ≤ 1000$) —— 集合 $S$ 的大小。第二行包含 $m$ 个整数 $s_1, s_2, ..., s_m$ ($1 ≤ s_i ≤ 10^6$) —— 集合 $S$ 的元素。保证集合元素按严格递增顺序给出，即 $s_1 < s_2 < ... < s_m$。\n\n## Output\n\n如果没有解，输出一行 _-1_。否则，第一行输出一个整数 $n$，表示序列的长度，$n$ 不应超过 $4000$。第二行输出 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^6$) —— 序列。我们可以证明，如果存在解，则一定存在一个满足 $n$ 不超过 $4000$ 且所有 $a_i$ 不超过 $10^6$ 的解。如果有多个解，输出任意一个即可。\n\n[samples]\n\n## Note\n\n在第一个例子中，$2 = gcd(4, 6)$，集合中的其他元素出现在序列中，我们可以证明在所有 $1 ≤ i ≤ j ≤ n$ 的 $gcd(a_i, a_{i+1}, ..., a_j)$ 中，不存在除 $2$、$4$、$6$ 和 $12$ 以外的值。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ S = \\{s_1, s_2, \\dots, s_m\\} $ with $ s_1 < s_2 < \\dots < s_m $.\n\n**Definitions:**\n- Let $ G $ be the set of all GCDs of contiguous subsequences of some sequence $ A = [a_1, a_2, \\dots, a_n] $.\n- We are given $ S = G $, and must find such a sequence $ A $, or determine that none exists.\n\n**Constraints:**\n1. $ S $ must be closed under GCD: for any $ x, y \\in S $, $ \\gcd(x, y) \\in S $.\n2. The largest element $ s_m $ must appear as some $ a_i $, because $ \\gcd(a_i) = a_i $, and no GCD of a subsequence can exceed the maximum element in the sequence.\n3. Every element of $ S $ must be the GCD of some contiguous subsequence of $ A $.\n\n**Necessary condition for existence:**\n- For every $ x \\in S $, $ x $ must divide $ s_m $ (since all GCDs must divide the maximum element of the sequence, which is at most $ s_m $, and $ s_m \\in S $).\n- $ S $ must be closed under GCD: $ \\forall x, y \\in S, \\gcd(x, y) \\in S $.\n\n**Construction (if condition holds):**\nLet $ A = [s_1, s_2, \\dots, s_m] $.  \nThen the set of GCDs of contiguous subsequences of $ A $ is exactly $ S $ **if and only if** $ S $ is closed under GCD and every element divides $ s_m $.\n\nBut this simple construction does **not** always work.\n\n**Better construction (known from similar problems):**\n- Let $ A = [s_1, s_2, s_1, s_3, s_1, s_4, \\dots, s_1, s_m] $.  \n  That is, interleave $ s_1 $ with each $ s_i $ for $ i = 2 $ to $ m $:  \n  $$\n  A = [s_1, s_2, s_1, s_3, s_1, s_4, \\dots, s_1, s_m]\n  $$\n- Length: $ n = 2m - 1 $\n\n**Why this works:**\n- Every $ s_i $ appears as a singleton → $ s_i \\in G $.\n- $ \\gcd(s_i, s_1) = \\gcd(s_i, s_1) $. Since $ s_1 $ is the smallest element and $ S $ is GCD-closed, $ \\gcd(s_i, s_1) = s_1 $ (because $ s_1 \\mid s_i $, as $ s_1 $ is the GCD of all elements in $ S $).\n- All GCDs of contiguous subsequences are elements of $ S $, because $ S $ is GCD-closed and all elements divide $ s_m $.\n\n**Key insight:**\n- Since $ S $ is GCD-closed, $ s_1 = \\gcd(S) $, and $ s_1 \\mid s_i $ for all $ i $.\n- So $ \\gcd(s_i, s_1) = s_1 $, and any GCD of a contiguous subsequence involving multiple elements will be a GCD of some subset of $ S $, hence in $ S $.\n\n**Algorithm:**\n1. Check if $ s_1 = \\gcd(s_1, s_2, \\dots, s_m) $. (Must hold, since $ s_1 $ is the minimal element and GCD-closed implies it divides all.)\n2. Check closure: for all $ i, j $, $ \\gcd(s_i, s_j) \\in S $.\n3. If not, output `-1`.\n4. Otherwise, construct $ A = [s_1, s_2, s_1, s_3, s_1, s_4, \\dots, s_1, s_m] $.\n\n**Formal Output:**\n\nGiven:  \n- $ S = \\{s_1, s_2, \\dots, s_m\\} $, $ s_1 < s_2 < \\dots < s_m $, $ s_i \\in \\mathbb{Z}^+ $\n\nDefine:  \n- $ d = \\gcd(S) $. Must equal $ s_1 $.  \n- For all $ i, j \\in [1, m] $, $ \\gcd(s_i, s_j) \\in S $.\n\nIf not satisfied:  \n Output: `-1`\n\nElse:  \n Let $ n = 2m - 1 $  \n Let $ A = [s_1, s_2, s_1, s_3, s_1, s_4, \\dots, s_1, s_m] $  \n Output $ n $  \n Output $ A $\n\n**Note:** This construction ensures all $ s_i $ appear as singletons, and all pairwise GCDs between $ s_i $ and $ s_1 $ yield $ s_1 $, and any longer GCDs are GCDs of elements of $ S $, hence in $ S $ by closure. No extraneous values are introduced because $ S $ is closed and all elements divide $ s_m $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF894C","tags":["constructive algorithms","math"],"sample_group":[["4\n2 4 6 12","3\n4 6 12"],["2\n2 3","\\-1"]],"created_at":"2026-03-03 11:00:39"}}