有理数逼近

【题目描述】

给定 $T$ 组测试数据。对每组数据，求解下面的问题。

给定正整数 $N, x, y$。设 $S$ 为分子与分母都是不超过 $N$ 的正整数且不可约的分数构成的集合。求 $S$ 中小于等于 $x/y$ 的最大值（若不存在则为 $0/1$），以及 $S$ 中大于等于 $x/y$ 的最小值（若不存在则为 $1/0$）。

【输入】

$T$
$N_0$ $x_0$ $y_0$
$N_1$ $x_1$ $y_1$
$\vdots$
$N_{T-1}$ $x_{T-1}$ $y_{T-1}$

【输出】

输出 $T$ 行。当两个值分别为 $a/b$ 和 $c/d$ 时，每行按如下格式输出。

$a$ $b$ $c$ $d$

【输入样例】

5
7 3 10
9 3 6
2 7 3
500 314159265 100000000
100000000 198264837 861210737

【输出样例】

2 7 1 3
1 2 1 2
2 1 1 0
333 106 355 113
10885117 47282109 14189579 61635830

【数据范围】

• $1 \leq T \leq 100000$
• $1 \leq N, x, y \leq 1000000000$

【来源】

Library Checker（yosupo06） rational_approximation