Positive Solutions of Linear Diophantine Equations

Given a linear Diophantine equation in two variables

$$ax+by=c$$

There are three cases to consider:

1. If the equation has no integer solution, output \(-1\).
2. If the equation has integer solutions and there exists at least one solution with both \(x>0\) and \(y>0\) (i.e. a positive solution), then output five numbers:
1. The number of positive solutions.
2. The minimum value of \(x\) among all positive solutions.
3. The minimum value of \(y\) among all positive solutions.
4. The maximum value of \(x\) among all positive solutions.
5. The maximum value of \(y\) among all positive solutions.
3. If the equation has integer solutions but no positive solution (i.e. no solution where both \(x\) and \(y\) are positive), then output two numbers:
   1. The smallest positive integer value of \(x\) among all integer solutions (i.e. considering only those solutions where \(x>0\)).
   2. The smallest positive integer value of \(y\) among all integer solutions (i.e. considering only those solutions where \(y>0\)).

Note:

• A positive solution is one in which both \(x>0\) and \(y>0\). Zero is not considered a positive integer.
• An integer solution is any pair \((x,y)\) where \(x\) and \(y\) are integers satisfying the equation.

The general solution of the equation (when at least one solution exists) is given by:

$$x=x_0+\frac{b}{d}t,\quad y=y_0-\frac{a}{d}t$$

where \(d=\gcd(a,b)\) and \((x_0,y_0)\) is a particular solution of \(ax+by=c\). To obtain the positive solutions, determine the range of the integer parameter \(t\) such that \(x\ge1\) and \(y\ge1\).

inputFormat

The input consists of a single line containing three space‑separated integers \(a\), \(b\), and \(c\).

outputFormat

If the equation does not have any integer solution, output -1.

If the equation has a positive solution, output 5 space‑separated integers: the number of positive solutions, the minimum \(x\), the minimum \(y\), the maximum \(x\), and the maximum \(y\) among all positive solutions.

If the equation has integer solutions but no positive solution, output 2 space‑separated integers: the smallest positive \(x\) (among the solutions with \(x>0\)) and the smallest positive \(y\) (among the solutions with \(y>0\)).

sample

4 6 8

2 2