use std::collections::*; use std::io::Write; type Map = BTreeMap; type Set = BTreeSet; type Deque = VecDeque; fn main() { input! { t: usize, ask: [(u64, u64, u64); t], } for (n, l, r) in ask { if let Some((a, b, c)) = solve(n, l, r) { let mut a = [a, b, c]; a.sort(); use util::*; println!("{}", a.iter().join(" ")); } else { println!("-1"); } } } fn solve(mut n: u64, l: u64, r: u64) -> Option<(u64, u64, u64)> { if n == 1 { return None; } let mut d = vec![(1u64, 0)]; let mut k = 0; let mut extend = |p: u64, c: usize| { let len = d.len(); for i in 0..c { for j in 0..len { let mut q = d[d.len() - len]; q.0 *= p; if i + 1 == c { q.1 |= 1 << k; } d.push(q); } } k += 1; }; let mut p = 2; while p * p <= n { let mut c = 0; while n % p == 0 { n /= p; c += 1; } if c > 0 { extend(p, c); } p += 1; } if n > 1 { extend(n, 1); } d.retain(|p| l <= p.0 && p.0 <= r); let c = k; let mut bit = vec![vec![]; 1 << k]; for (p, x) in d { if bit[x].len() < 3 { bit[x].push((p, x)); } } let d = bit.into_iter().flatten().collect::>(); let m = d.len(); for i in 0..m { for j in 0..i { for k in 0..j { if d[i].1 | d[j].1 | d[k].1 == (1 << c) - 1 { return Some((d[i].0, d[j].0, d[k].0)); } } } } None } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- mod util { pub trait Join { fn join(self, sep: &str) -> String; } impl Join for I where I: Iterator, T: std::fmt::Display, { fn join(self, sep: &str) -> String { let mut s = String::new(); use std::fmt::*; for (i, v) in self.enumerate() { if i > 0 { write!(&mut s, "{}", sep).ok(); } write!(&mut s, "{}", v).ok(); } s } } }