/* -*- coding: utf-8 -*- * * 3663.cc: No.3663 LCM Decomposition - yukicoder */ #include #include #include #include #include using namespace std; /* constant */ const int MAX_P = 32000; const int MAX_K = 9; const int KBITS = 1 << MAX_K; /* typedef */ using vb = vector; using vi = vector; using si = set; using pii = pair; using vpii = vector; /* global variables */ vb primes; vi pnums; int eps[MAX_K], cs[MAX_K]; vi bds[KBITS]; si bqs[KBITS]; /* subroutines */ int gen_primes(int maxp) { primes.assign(maxp + 1, true); primes[0] = primes[1] = false; pnums.clear(); int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums.push_back(p); for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums.push_back(p); return (int)pnums.size(); } vpii prime_decomp(int n) { vpii pds; for (auto pi: pnums) { if (pi * pi > n) { if (n > 1) pds.push_back(pii(n, 1)); break; } if (n % pi == 0) { int fi = 0; while (n % pi == 0) n /= pi, fi++; pds.push_back(pii(pi, fi)); } } return pds; } int powi(int a, int b) { int p = 1; while (b > 0) { if (b & 1) p *= a; a *= a; b >>= 1; } return p; } int powi(pii &pd) { return powi(pd.first, pd.second); } int pds2i(vpii &pds) { int n = 1; for (auto [p, d]: pds) n *= powi(p, d); return n; } vi merge(si &bq0, si &bq1, si &bq2) { for (auto q0: bq0) for (auto q1: bq1) if (q0 != q1) for (auto q2: bq2) if (q0 != q2 && q1 != q2) { vi v{q0, q1, q2}; sort(v.begin(), v.end()); return v; } return {}; } /* main */ int main() { gen_primes(MAX_P); int tn; scanf("%d", &tn); while (tn--) { int n, l, r; scanf("%d%d%d", &n, &l, &r); auto pds = prime_decomp(n); int k = (int)pds.size(); for (int i = 0; i < k; i++) eps[i] = powi(pds[i]); //for (int i = 0; i < k; i++) printf(" %d", eps[i]); putchar('\n'); vi ds; for (int p = 1; p * p <= n; p++) if (n % p == 0) { if (l <= p && p <= r) ds.push_back(p); int q = n / p; if (q != p && l <= q && q <= r) ds.push_back(q); } if (ds.size() < 3) { puts("-1"); continue; } sort(ds.begin(), ds.end()); //for (auto d: ds) printf(" %d", d); putchar('\n'); int kbits = 1 << k; for (int bits = 0; bits < kbits; bits++) bds[bits].clear(); for (auto d: ds) { int bits = 0; for (int i = 0, bi = 1; i < k; i++, bi <<= 1) if (d % eps[i] == 0) bits |= bi; if (bds[bits].size() < 3) bds[bits].push_back(d); } //for (int bits = 0; bits < kbits; bits++) { // printf(" %d:", bits); // for (auto d: bds[bits]) printf(" %d", d); putchar('\n'); //} for (int bits = 0; bits < kbits; bits++) bqs[bits].clear(); for (int i = 0; i < 3; i++) bqs[0].insert(ds[i]); for (int bits = 1; bits < kbits; bits++) { for (int bits0 = bits; bits0 > 0; bits0 = (bits0 - 1) & bits) for (auto d: bds[bits0]) { if (bqs[bits0].size() >= 3) break; bqs[bits0].insert(d); } } //for (int bits = 0; bits < kbits; bits++) { // printf(" %d:", bits); // for (auto q: bqs[bits]) printf(" %d", q); putchar('\n'); //} fill(cs, cs + k, 0); bool found = false; for (;;) { int bits[3] = {}; for (int i = 0; i < k; i++) bits[cs[i]] |= (1 << i); auto v = merge(bqs[bits[0]], bqs[bits[1]], bqs[bits[2]]); if (! v.empty()) { printf("%d %d %d\n", v[0], v[1], v[2]); found = true; break; } int l = 0; while (l < k) { if (++cs[l] > 2) cs[l++] = 0; else break; } if (l >= k) break; } if (! found) puts("-1"); } return 0; }