P5656 [Template] Binary Linear Diophantine Equation (exgcd)

Given the indeterminate equation $$ax+by=c$$ If this equation has no integer solution, output $-1$. If this equation has integer solutions and also has positive integer solutions, output: the number of **positive integer** solutions, the minimum value of $x$ among all **positive integer** solutions, the minimum value of $y$ among all **positive integer** solutions, the maximum value of $x$ among all **positive integer** solutions, and the maximum value of $y$ among all **positive integer** solutions. If the equation has integer solutions but has no positive integer solution, you need to output: the minimum positive integer value of $x$ among all **integer solutions**, and the minimum positive integer value of $y$ among all **integer solutions**. A positive integer solution means a solution where both $x$ and $y$ are positive integers, and $\boldsymbol{0}$ **is not a positive integer**. An integer solution means a solution where both $x$ and $y$ are integers. The minimum positive integer value of $x$ means the minimum value of $x$ among all integer solutions with $x$ being a positive integer, and similarly for $y$.

The first line contains a positive integer $T$, representing the number of test cases. The next $T$ lines each contain three positive integers $a, b, c$ separated by spaces.

Output $T$ lines. If the corresponding query has no integer solution, output a single number $-1$. If the corresponding query has integer solutions but no positive integer solution, output $2$ numbers separated by spaces, representing the minimum positive integer value of $x$ and the minimum positive integer value of $y$ among integer solutions, in order. Otherwise, output $5$ numbers separated by spaces, representing the number of positive integer solutions, the minimum $x$, the minimum $y$, the maximum $x$, and the maximum $y$ among positive integer solutions, in order. The input and output sizes are large, so please use fast I/O methods.

**Constraints** For $100\%$ of the testdata, $1 \le T \le 2 \times {10}^5$, $1 \le a, b, c \le {10}^9$. Translated by ChatGPT 5