题目背景

P11036 GCD 与 LCM 问题

本题与 P11036 的差别仅在数据范围和对 $b,c,d$ 的范围限制。

---

:::align{center}

「既然你说你不了解她，为什么又可以断言她一定是因为……」

是呀，自己对零羽还了解的确实不够多……泠珞这样想着。

在残缺的记忆当中，她只能想起，她和零羽的最大公约数，就是「音乐」。

还缺了什么呢？泠珞不知道。她只知道，那所缺失的，和「音乐」加起来，就是她的一切的总和。

这样的自己，比起她，是多么渺小啊……

:::

题目描述

给定一个正整数 $a$，请你找出三个正整数 $b,c,d$ 使得 $a+b+c+d=\gcd(a,b)+\operatorname{lcm}(c,d)$。一个测试点内有多组数据。

由于出题人不想把自己 QQ 号写题目里，你需要保证 $b,c,d\le \color{red}49\, 999$。

如有多种可能的答案，输出任意一个均可。

输入格式

第一行一个正整数 $t$ 表示数据组数。

接下来 $t$ 行每行一个正整数 $a$。

输出格式

输出 $t$ 行，每行三个正整数 $b,c,d$。

如有多种可能的答案，输出任意一个均可。

4
1
2
3
20120712

7 9 2
9 6 8
5 9 2
10429 8888 9068

提示

【样例解释】

样例的输出为：

$1+7+9+2=19=\gcd(1,7)+\operatorname{lcm}(9,2)$
$2+9+6+8=25=\gcd(2,9)+\operatorname{lcm}(6,8)$
$3+5+9+2=19=\gcd(3,5)+\operatorname{lcm}(9,2)$
$20\,120\,712+10\,429+8\,888+9\,068=20\,149\,097=\gcd(20\,120\,712,10\,429)+\operatorname{lcm}(8\,888,9\,068)$

容易验证均满足要求。

【数据范围】

本题采用捆绑测试。

Subtask 编号	分数	$t\le$	$a\le$	特殊性质
$1$	$3$	$32\ 767$
$2$	$5$	$59\ 999$
$3$	$19$	$10^4$	$10^8$	$\textbf{AB}$
$4$	$31$	$3\times10^5$	$10^9$	$\textbf{A}$
$5$	$29$		$10^9-1$	$\textbf{B}$
$6$	$13$		$10^9$

特殊性质 $\textbf{A}$：所有 $a$ 在数据范围内独立均匀随机生成。

特殊性质 $\textbf{B}$：$a$ 是奇数。

对于 $100\%$ 的数据，$1\le t\le3\times10^5$，$1\le a\le 10^9$。