有理数逼近 (Rational Approximation)

时间限制：5 秒

题目描述

给定 $T$ 组测试数据。对于每组数据，解决以下问题。

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

约束条件

• $1 \le T \le 10^5$
• $1 \le N, x, y \le 10^9$

输入

T
N_0 x_0 y_0
N_1 x_1 y_1
⋮
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