Minimum Attainable Value

You are given three nonnegative integers \(x\), \(a\), and \(b\). Under the transformation

[ x \to a,x - b, ]

you are allowed to perform the operation any number of times (including zero), as long as the resulting \(x\) remains nonnegative. In other words, if you have a current value \(x\), you may update it to \(a\,x - b\) only when \(a\,x - b \ge 0\). Your task is to determine the minimum value of \(x\) that can be obtained by applying this operation optimally.

Note:

• If the operation is not beneficial or cannot be applied, you may choose not to perform any operations, and the answer will simply be the initial \(x\).
• In the case \(a = 1\), the operation reduces to \(x \to x - b\); hence repeatedly applying it gives \(x - n\,b\). The optimal result is \(x \bmod b\) (if \(b > 0\)).
• For \(a > 1\), observe that the difference between successive values is given by \[ f(n+1) - f(n) = a^n\,\bigl((a-1)x - b\bigr), \] so if \((a-1)x \ge b\) then any operation would only increase \(x\), making it optimal to perform zero operations.

inputFormat

The input consists of a single line containing three space-separated nonnegative integers: \(x\), \(a\), and \(b\).

outputFormat

Output a single integer — the minimum nonnegative value of \(x\) that can be obtained by applying the operation \(x \to a\,x - b\) optimally.

sample

4 3 10

2