【模板】二元一次不定方程 (exgcd)

题目背景

从前,有一个很强的小朋友叫做 $\text{\color{black}{L}}\text{\color{red}{iM}}$,小学**奥术**课上,老师给她留了一道求二元一次不定方程的解的题。她一眼秒掉后睡了一节课,她现在要拿 $\text{exgcd}$ 模板题来考考您。 ~~如果您熟练地解决了这道题,那么 $\text{\color{black}{L}}\text{\color{red}{iM}}$ 会萌萌地跟您说“为什么你会这么熟...~~

题目描述

给定不定方程 $$ax+by=c$$ 若该方程无整数解,输出 $-1$。 若该方程有整数解,且有正整数解,则输出其**正整数**解的数量,所有**正整数**解中 $x$ 的最小值,所有**正整数**解中 $y$ 的最小值,所有**正整数**解中 $x$ 的最大值,以及所有**正整数**解中 $y$ 的最大值。 若方程有整数解,但没有正整数解,你需要输出所有**整数解**中 $x$ 的最小正整数值, $y$ 的最小正整数值。 正整数解即为 $x, y$ 均为正整数的解,$\boldsymbol{0}$ **不是正整数**。 整数解即为 $x,y$ 均为整数的解。 $x$ 的最小正整数值即所有 $x$ 为正整数的整数解中 $x$ 的最小值,$y$ 同理。

输入输出格式

输入格式


第一行一个正整数 $T$,代表数据组数。 接下来 $T$ 行,每行三个由空格隔开的正整数 $a, b, c$。

输出格式


$T$ 行。 若该行对应的询问无整数解,一个数字 $-1$。 若该行对应的询问有整数解但无正整数解,包含 $2$ 个由空格隔开的数字,依次代表整数解中,$x$ 的最小正整数值,$y$ 的最小正整数值。 否则包含 $5$ 个由空格隔开的数字,依次代表正整数解的数量,正整数解中,$x$ 的最小值,$y$ 的最小值,$x$ 的最大值,$y$ 的最大值。 **读入输出量较大,注意使用较快的读入输出方式**

输入输出样例

输入样例 #1

7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432

输出样例 #1

4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56

说明

**【数据范围】** 对于 $100\%$ 的数据,$1 \le T \le 2 \times {10}^5$,$1 \le a, b, c \le {10}^9$。