Промежуточное

using namespace std;

#include <algorithm>
#include <map>

#ifdef DEBUG
#include <fstream>
ifstream IN("input.txt");
ofstream OUT("output.txt");
#endif

#ifndef DEBUG
#include <iostream>
#define IN cin
#define OUT cout
#endif

map<int, bool> pr;
map<int, bool> prs;
map<int, pair<int, int>> nxt;

int n;

int main() {
    ios_base::sync_with_stdio(0);
    IN >> n;
    int x;
    int max = 0;
    int chkd = 3;
    prs[2] = true;
    for (int i = 0; i < n; ++i) {
        IN >> x;
        if (pr[x]) {
            while (pr[x]) {
                OUT << nxt[x].first << " ";
                x = nxt[x].second;
            }
            if (x > 1) {
                OUT << x;
            }
            OUT << endl;
        }
        else if (prs[x]) OUT << x << endl;
        else {
            while (!(x % 2)) {
                OUT << "2 ";
                pr[x] = true;
                int y = x / 2;
                nxt[x] = { 2, x / 2 };
                x = y;
            }
            int sx = x;
            while (!pr[x] && !prs[x]) {
                bool f = false;
                int j = 3;
                while ((j <= sqrt(x) && !f)) {
                    if (!(x % j)) {
                        prs[j] = true;
                        f = true;
                        pr[x] = true;
                        int y = x / j;
                        nxt[x] = { j, y };
                        OUT << j << " ";
                        x = y;
                    }
                    j += 2;
                }
                if (!f) {
                    prs[x] = true;
                }
            }
            while (pr[x]) {
                OUT << nxt[x].first << " ";
                x = nxt[x].second;
            }
            if (x > 1) {
                OUT << x;
            }
            OUT << endl;
        }
    }
}