GCD、LCM 与欧几里得算法

// 标准答案 —— **按定义算**：把每个数分解质因数，gcd 取指数的 min，lcm 取 max。
//
// 为什么它存在：这是和欧几里得**完全不同的一条思路**（第 9、15 章那条规矩：
// 标准答案最好换个想法写，同一个想法写两遍只能验出打字错误）。
//   · 欧几里得：不管这些数长什么样，只反复取模；
//   · 这一份：**真的把质因数摆出来** —— gcd 是「每个质因子各取最少的那份」，
//     lcm 是「各取最多的那份」。定义就长这样。
//
// ★ 顺带把一条重要的等式摆在了明处：**gcd(a,b) × lcm(a,b) = a × b**
//   （每个质因子的 min + max = 两个指数之和）。正文里那句「先除后乘」就是从这来的。
//
// ⚠ 它慢在哪：试除要到 √a（10⁹ 时是 31623 步），所以是 O(n√A) ——
//   比欧几里得的 O(n log A) 慢得多，可比「从 min 往下枚举」（slow.cpp，O(min(a,b))）快得多。
//   ⇒ 这一章一共有**三种**求 gcd 的办法，慢的方式各不相同，第 4、5 步会摆成一张表。

#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 试除分解：返回 {质因子, 指数} */
static map<long long, int> factor(long long x) {
    map<long long, int> f;
    for (long long p = 2; p * p <= x; p++)
        while (x % p == 0) { f[p]++; x /= p; }
    if (x > 1) f[x]++;                             // ⚠ 剩下的那个也是质因子（可能很大）
    return f;
}

/** 把 {质因子, 指数} 乘回一个数；超过 LIM 就报告溢出 */
static bool build(const map<long long, int>& f, long long& out) {
    long long v = 1;
    for (auto& [p, e] : f)
        for (int k = 0; k < e; k++) {
            if (v > LIM / p) return false;         // ⚠ 乘之前先判
            v *= p;
        }
    out = v;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    vector<map<long long, int>> fs(n);
    for (int i = 0; i < n; i++) fs[i] = factor(a[i]);

    // gcd：每个质因子取**最少**的那份（只有大家都有的质因子才留得下）
    map<long long, int> gf = fs[0];
    for (int i = 1; i < n; i++) {
        map<long long, int> nf;
        for (auto& [p, e] : gf) {
            auto it = fs[i].find(p);
            if (it != fs[i].end()) nf[p] = min(e, it->second);
        }
        gf = nf;
    }
    long long g = 1;
    build(gf, g);

    // lcm：每个质因子取**最多**的那份
    map<long long, int> lf;
    for (int i = 0; i < n; i++)
        for (auto& [p, e] : fs[i]) lf[p] = max(lf[p], e);
    long long l = 0;
    bool ok = build(lf, l);

    printf("%lld\n", g);
    printf("%lld\n", ok ? l : -1LL);

    // ★ 第三行：前缀 gcd —— 一边扫一边把「取 min」做下去
    map<long long, int> pf = fs[0];
    for (int i = 0; i < n; i++) {
        if (i) {
            map<long long, int> nf;
            for (auto& [p, e] : pf) {
                auto it = fs[i].find(p);
                if (it != fs[i].end()) nf[p] = min(e, it->second);
            }
            pf = nf;
        }
        long long cur = 1;
        build(pf, cur);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ⚠ 这不是错误版本 —— 答案和正解**逐字节相同**，只是求 gcd 的办法最老实：
//   **从 min(a,b) 往下一个个试，第一个同时整除两个数的就是最大公约数。**
//
// 为什么它存在：这是这一章耗时表里**最慢**的那一支，而且它慢得很好懂 ——
//   gcd(a,b) 要转 **min(a,b) − gcd(a,b) + 1** 圈。a、b 都取到 10⁹ 而又互质的话，
//   它要转整整十亿圈。
//
// ★ 这一章一共三种求 gcd 的办法，而它们慢的**原因各不相同**（正文第 5 步那张表）：
//   · slow（枚举约数）：慢在**min(a,b) 有多大** —— 只看规模；
//   · sub （更相减损）：慢在**a 和 b 差得有多远** —— 看的是两个数的比例；
//   · brute（分解质因数）：慢在**√a** —— 又是另一条曲线。
//   ⇒ 想让哪一支现形，要拧的旋钮根本不是同一个（第 36 章那条的又一次）。
//
// ⚠ 所以正文里那张耗时表**必须给出不止一个形状的数据**，只报一列谁都能被冤枉。

#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;

/** 枚举法求 gcd：从 min(a,b) 往下找第一个同时整除的 */
long long gcdSlow(long long a, long long b) {
    if (a == 0) return b;
    if (b == 0) return a;
    for (long long d = min(a, b); d >= 1; d--)
        if (a % d == 0 && b % d == 0) return d;
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcdSlow(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long t = l / gcdSlow(l, a[i]);
        if (t > LIM / a[i]) over = true;
        else l = t * a[i];
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcdSlow(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ⚠ 这不是错误版本 —— 它的答案和正解**逐字节相同**，只是把「取模」换成了「相减」。
//
// 更相减损术（《九章算术》里那个）：**gcd(a,b) = gcd(a−b, b)**（a > b）。
// 证明和取模版一模一样（公约数集合不变），而且取模本来就是「连着减很多次」的缩写。
//
// ★ 于是它成了这一章的「第四个盲区」现场（第 36 章立的）：
//   **只影响复杂度、不影响答案的写法，对拍原理上一个字都看不见。**
//   gcd(10⁹, 1) 这种输入，取模版一步到头，减法版要减 **10⁹ 次**。
//   ⇒ 尺子只能换成「数圈数」：count.cpp 数的就是这个。
//
// ⚠ 而且这一章的两份「慢」是**两种不同的慢**，正文里要分开讲：
//   · brute（枚举约数）：慢在**要试到 min(a,b)**；
//   · sub（相减）：慢在**a 和 b 差得越远越慢**（一次只减掉一个 b）。
//   前者只看规模，后者看的是**两个数的比例** —— 生成器要拧的旋钮根本不是同一个。

#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;

/** 更相减损术：大的减小的，减到两个数相等 */
long long gcdSub(long long a, long long b) {
    if (a == 0) return b;
    if (b == 0) return a;
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcdSub(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long t = l / gcdSub(l, a[i]);
        if (t > LIM / a[i]) over = true;
        else l = t * a[i];
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcdSub(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// 正解 —— 欧几里得算法（辗转相除）
//
// ============ ★ 关键一步：一行就能证完 ============
//
//   **gcd(a, b) = gcd(b, a mod b)**（b ≠ 0）
//
//   证明只要看**公约数的集合**，而不是 gcd 那个最大值本身：
//     设 a = k·b + r（r = a mod b）。
//     · 若 d | b 且 d | r，则 d | (k·b + r) = a  ⇒ d 是 (a,b) 的公约数；
//     · 若 d | a 且 d | b，则 d | (a − k·b) = r  ⇒ d 是 (b,r) 的公约数。
//   ⇒ **两对数的公约数集合完全相同**，那么其中最大的那个当然也相同。∎
//
//   ★ 这一步值钱的地方在于「证的是集合相等」：
//     直接去比两个 max 谁大谁小是证不动的，把问题换成「集合」就一行完事。
//     （第 19 章交换论证、第 34 章切割性质，都是同一种手法：**别盯着最优解，去看一个更大的对象**。）
//
// ============ 为什么它快 ============
//
//   每**两步**规模至少减半：看 a mod b（设 a ≥ b）——
//     · 若 b ≤ a/2，则 a mod b < b ≤ a/2；
//     · 若 b > a/2，则 a mod b = a − b < a/2。
//   两种情况都得到 **a mod b < a/2**，所以两步之内第一个数至少减半 ⇒ **O(log)**。
//
//   ⚠ 但这只是个上界。真正的最坏情况是**相邻的斐波那契数**（Lamé 定理），
//     而随机数据**永远碰不到它** —— steps.cpp 把这两列并排量出来了。
//
// ============ ⚠ 三个边界，一个都不能想当然 ============
//
//   · gcd(a, 0) = a  ——「0 被所有数整除」，所以循环条件是 `while (b)`；
//   · lcm 必须**先除后乘**：`a / gcd(a,b) * b`。写成 `a * b / gcd` 中间就爆 long long；
//   · 求 n 个数的 lcm 时**一超过上限就得停**，否则后面那些乘法照样会溢出。
//
// 复杂度 O(n log A)。

#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b) {                                    // ⚠ 是 while (b)，不是 while (a)
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcd2(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long t = l / gcd2(l, a[i]);           // ⚠ 先除后乘
        if (t > LIM / a[i]) over = true;           // 乘之前先判会不会超
        else l = t * a[i];
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcd2(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ✗ 错误版本：循环条件写成 `while (b > 1)`（「b 都到 1 了，肯定就是 1，可以停」）
//
//   ✗ 停是可以停，**可返回值写错了**：这时候答案是 1，它却把 a 返回了出去。
//
// 靠什么现形：某一次 gcd 的中间步骤里出现 `b == 1` 而 `a > 1` ——
//   也就是**那一对数互质**。随机数据上这件事的概率是 6/π² ≈ 60.8%，所以它非常好抓。
// ★ 它在这一章里的角色和第 38 章的 wrongDir 一样：**基线**。
#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b > 1) {                                // ✗ 到 1 就停了，可返回的还是 a
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcd2(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long t = l / gcd2(l, a[i]);           // ⚠ 先除后乘
        if (t > LIM / a[i]) over = true;           // 乘之前先判会不会超
        else l = t * a[i];
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcd2(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ✗ 错误版本：「gcd 已经是 1 了，后面不用算了」—— 把整个循环 break 掉
//
//   `if (g == 1) break;` 这句话对**第一行**（全体 gcd）来说完全正确：
//   gcd 一旦变成 1 就再也变不回去。
//   ✗ 可它顺手把**后面那些数也跳过了**，于是这些数根本没参与 lcm 和前缀 gcd。
//
// 靠什么现形：全体 gcd 中途变成 1，**而且后面还有数**。
// ★ 这个 bug 的形状值得记：**一个只对「其中一问」成立的剪枝，被顺手用在了整个循环上。**
//   （第 35 章那条「同一个顺手写法在同一道题的两问里效果相反」的近亲。）
#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b) {                                    // ⚠ 是 while (b)，不是 while (a)
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    int stop = n;
    for (int i = 1; i < n; i++) {
        g = gcd2(g, a[i]);
        if (g == 1) { stop = i + 1; break; }        // ✗ 后面那些数被整个跳过了
    }

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < stop && !over; i++) {
        long long t = l / gcd2(l, a[i]);           // ⚠ 先除后乘
        if (t > LIM / a[i]) over = true;           // 乘之前先判会不会超
        else l = t * a[i];
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i && i < stop) cur = gcd2(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ✗ 错误版本：第三行的前缀 gcd 写成了**相邻两个数的 gcd**
//
//   g_i 应该是 gcd(a_1 … a_i)，这里写成了 gcd(a_{i−1}, a_i)。
//
// 靠什么现形：★★ 要 **gcd(a_{i−1}, a_i) ≠ gcd(a_1 … a_i)** ——
//   而随机数据上这两个数**几乎总是同时等于 1**（见 coprime.cpp：
//   两个随机数互质的概率是 6/π² ≈ 60.8%，n 个数的 gcd 是 1 的概率是 1/ζ(n)，n = 5 时就 96%）。
//   ⇒ **必须让数据带公因子**，否则这道题整个退化成「输出 1」，这个 bug 一轮都抓不到。
#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b) {                                    // ⚠ 是 while (b)，不是 while (a)
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcd2(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long t = l / gcd2(l, a[i]);           // ⚠ 先除后乘
        if (t > LIM / a[i]) over = true;           // 乘之前先判会不会超
        else l = t * a[i];
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    for (int i = 0; i < n; i++) {
        long long cur = i ? gcd2(a[i - 1], a[i]) : a[0];   // ✗ 只和前一个比，不是和前缀比
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ✗ 错误版本：**根本不判溢出**，一路乘下去
//
// 靠什么现形：只要**答案超过 10¹⁸** 就现形 —— 三个溢出 bug 里**门槛最低**的一个
//   （另外两个要撞破 long long 才算数）。
// ⚠ 所以它是这一组的「基线」：抓得住它，一点都不能说明值域拧够了。
#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b) {                                    // ⚠ 是 while (b)，不是 while (a)
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcd2(g, a[i]);

    long long l = a[0];
    bool over = false;                             // ✗ 它永远是 false
    for (int i = 1; i < n; i++)
        l = l / gcd2(l, a[i]) * a[i];              // ✗ 一路乘，超没超都不管

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcd2(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ✗ 错误版本：溢出判断**写在乘完之后**
//
//   long long t = l / gcd(l, a[i]);
//   l = t * a[i];              ← ✗ 先乘
//   if (l > LIM) over = true;  ← ✗ 再判：可这时候 l 早就绕回去了
//
// 靠什么现形：★★ 和 wrongLcm 一样，要 `t × a[i]` 撞破 **long long** ——
//   只要没撞破，「乘完再判」和「乘前判」给的答案**一模一样**。
// ★ 这是这一章最阴的一个：判断逻辑本身写对了，**只是站错了位置**。
#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b) {                                    // ⚠ 是 while (b)，不是 while (a)
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcd2(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long t = l / gcd2(l, a[i]);
        l = t * a[i];                              // ✗ 先乘
        if (l > LIM) over = true;                  // ✗ 再判 —— 已经晚了
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcd2(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// ✗ 错误版本：lcm **先乘后除**（`l * a[i] / g` 而不是 `l / g * a[i]`）
//
// 靠什么现形：★ 要 `l × a[i]` 撞破 **long long**（约 9.2×10¹⁸）——
//   注意这比题面那个 10¹⁸ 的上限**还要大一截**：光是「答案超过 10¹⁸」还抓不到它。
//   ⇒ 要的是**值域拧满 ＋ 数之间别有太大的公因子**（有公因子 lcm 就涨不快）。
// ⚠ 这一章一共三个和溢出有关的 bug，它们要的条件**一个比一个苛刻**，正文里有一张表。
#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b) {                                    // ⚠ 是 while (b)，不是 while (a)
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcd2(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long p = l * a[i];                    // ✗ 先乘：这一句就已经溢出了
        long long t = p / gcd2(l, a[i]);
        if (t > LIM) over = true;
        else l = t;
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcd2(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

// 正解 —— 欧几里得算法（辗转相除）
//
// ============ ★ 关键一步：一行就能证完 ============
//
//   **gcd(a, b) = gcd(b, a mod b)**（b ≠ 0）
//
//   证明只要看**公约数的集合**，而不是 gcd 那个最大值本身：
//     设 a = k·b + r（r = a mod b）。
//     · 若 d | b 且 d | r，则 d | (k·b + r) = a  ⇒ d 是 (a,b) 的公约数；
//     · 若 d | a 且 d | b，则 d | (a − k·b) = r  ⇒ d 是 (b,r) 的公约数。
//   ⇒ **两对数的公约数集合完全相同**，那么其中最大的那个当然也相同。∎
//
//   ★ 这一步值钱的地方在于「证的是集合相等」：
//     直接去比两个 max 谁大谁小是证不动的，把问题换成「集合」就一行完事。
//     （第 19 章交换论证、第 34 章切割性质，都是同一种手法：**别盯着最优解，去看一个更大的对象**。）
//
// ============ 为什么它快 ============
//
//   每**两步**规模至少减半：看 a mod b（设 a ≥ b）——
//     · 若 b ≤ a/2，则 a mod b < b ≤ a/2；
//     · 若 b > a/2，则 a mod b = a − b < a/2。
//   两种情况都得到 **a mod b < a/2**，所以两步之内第一个数至少减半 ⇒ **O(log)**。
//
//   ⚠ 但这只是个上界。真正的最坏情况是**相邻的斐波那契数**（Lamé 定理），
//     而随机数据**永远碰不到它** —— steps.cpp 把这两列并排量出来了。
//
// ============ ⚠ 三个边界，一个都不能想当然 ============
//
//   · gcd(a, 0) = a  ——「0 被所有数整除」，所以循环条件是 `while (b)`；
//   · lcm 必须**先除后乘**：`a / gcd(a,b) * b`。写成 `a * b / gcd` 中间就爆 long long；
//   · 求 n 个数的 lcm 时**一超过上限就得停**，否则后面那些乘法照样会溢出。
//
// 复杂度 O(n log A)。

#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000000000000LL;      // 10¹⁸：题面说超过它就输出 -1

/** 辗转相除 —— 循环写法，b 变成 0 就到头了 */
long long gcd2(long long a, long long b) {
    while (b) {                                    // ⚠ 是 while (b)，不是 while (a)
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;                                      // ★ gcd(a, 0) = a
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long g = a[0];
    for (int i = 1; i < n; i++) g = gcd2(g, a[i]);

    long long l = a[0];
    bool over = false;
    for (int i = 1; i < n && !over; i++) {
        long long t = l / gcd2(l, a[i]);           // ⚠ 先除后乘
        if (t > LIM / a[i]) over = true;           // 乘之前先判会不会超
        else l = t * a[i];
    }

    printf("%lld\n", g);
    printf("%lld\n", over ? -1LL : l);

    // ★ 第三行：前缀 gcd —— g_i = gcd(a_1 … a_i)
    long long cur = a[0];
    for (int i = 0; i < n; i++) {
        if (i) cur = gcd2(cur, a[i]);
        printf("%lld%c", cur, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}