import std; void main () { int caseNum = readln.chomp.to!int; foreach (caseId; 0 .. caseNum) { int N, L, R; readln.read(N, L, R); if (N == 1) { writeln(-1); continue; } // a, b, cそれぞれ約数が必要条件 auto pfs = primeFactors(N); auto divs = divisors(N); divs = divs.arrayBSearch!((v) => v < L)[1].arrayBSearch!((v) => v <= R)[0]; if (divs.length < 3) { writeln(-1); continue; } auto S = new int[](divs.length); foreach (i; 0 .. divs.length) { foreach (idx, p; pfs.enumerate(0)) { long x = p[0] ^^ p[1]; if (divs[i] % x == 0) { S[i] |= 1 << idx; } } } auto cnt = new int[](1 << pfs.length); foreach (s; S) { if (cnt[s] == 0) { cnt[s]++; } } foreach (i; 0 .. pfs.length) { foreach (s; 0 .. pfs.length) { if (0 < (s & (1 << i))) { cnt[s ^ (1 << i)] += cnt[s]; } } } int[int] use; foreach (s; 0 .. 1 << pfs.length) { if (cnt[s] == 1) { use[s]++; } } auto vs = new Tuple!(int, int)[](0); foreach (i, s; S.enumerate(0)) { if (s in use) { vs ~= tuple(s, cast(int)(divs[i])); use.remove(s); } } auto dp = new Tuple!(int, int)[][](4, 1 << pfs.length); foreach (d; dp) { d[] = tuple(-int.max, 0); } dp[0][0] = tuple(-1, 0); foreach (val; vs) { foreach (i; 0 .. 4) { foreach (set; 0 .. 1 << pfs.length) { if (dp[i][set][0] == -int.max) { continue; } if (i + 1 <= 3 && set < (set | val[0])) { dp[i + 1][set | val[0]] = tuple(val[1], set); } } } } const int bt = (1 << pfs.length) - 1; bool ok = false; int[int] ans; foreach (i; 1 .. 4) { int cur = bt; int ci = i; if (0 < dp[ci][cur][0]) { while (cur != 0) { ans[dp[ci][cur][0]]++; cur = dp[ci][cur][1]; ci--; } ok = true; break; } } if (!ok) { writeln(-1); continue; } foreach (d; divs) { if (ans.length == 3) { break; } ans[cast(int)(d)]++; } auto used = ans.keys(); used.sort; writefln("%(%s %)", used); } } void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } import std.typecons : Tuple, tuple; Tuple!(long, int)[] primeFactors (long N) { import std.format : format; import std.exception; enforce(2 <= N && N <= 10L^^16, format("The argument %s is out of the allowable range. The valid range is [2, 10^16].", N)); Tuple!(long, int)[] res; foreach (i; 2..N) { if (N < 1L*i*i) break; if (N % i != 0) continue; int count = 0; while (N % i == 0) { N /= i; count++; } res ~= tuple(1L*i, count); } if (1 < N) res ~= tuple(N, 1); return res; } long[] divisors (ulong N) in { import std.format : format; assert(1 <= N && N <= 10L^^16, format("The argument %s is out of the allowable range. The valid range is [2, 10^16].", N)); } do { import std.algorithm : sort; long[] res; foreach (i; 1..N + 1) { if (N < 1L * i * i) break; if (N % i == 0) { res ~= i; if (1L * i * i < N) res ~= N / i; } } res.sort; return res; } /// 配列特化二分探索 /// fun: T -> boolが必要。また、一度falseになったら後ろが必ずfalseになるような述語を仮定。 /// fun: (int, T) -> boolにも対応済み /// 戻り値はスライス2個。 /// それぞれB1, B2としたとき、 /// B1の要素はfun(b1)がtrue /// B2の要素はfun(b2)がfalse import std.traits; T[][2] arrayBSearch (alias fun, T) (T[] A) if ((__traits(compiles, fun(T.init)) || __traits(compiles, fun(int.init, T.init))) && (is(typeof(fun(T.init)) == bool) || is(typeof(fun(int.init, T.init)) == bool)) ) { if (A.length == 0) { return [[], []]; } static if (__traits(compiles, fun(int.init, T.init))) { bool fi = fun(0, A[0]); } else { bool fi = fun(A[0]); } if (!fi) { return [[], A[]]; } int l = 0, r = cast(int)(A.length); while (1 < r - l) { int mid = (l + r) / 2; static if (__traits(compiles, fun(int.init, T.init))) { bool ok = fun(mid, A[mid]); } else { bool ok = fun(A[mid]); } if (ok) { l = mid; } else { r = mid; } } return [A[0 .. r], A[r .. $]]; }