Problem K
Square Bounce

Given a square in the plane with corners at $(-1,-1)$, $(-1,1)$, $(1,1)$ and $(1,-1)$, we fire a ray from point $(-1,0)$ into the interior of the square on a path with a given slope. The ray bounces off of the sides of the square with an angle of reflection which is the same as the angle of incidence to the side at the point of intersection.

After a number of bounces, the ray intersects one of the square’s sides again at some point which has rational coordinates. Find those rational coordinates in reduced form.

Input

The single line of input contains three integers $a$, $b$ and $n$ ($1 \le a,b,n \le 10^6$, $\gcd (a,b)=1$), where the slope of the ray’s initial path is $a/b$, and there are $n$ bounces. Note that $a$ and $b$ are relatively prime. The slope will be chosen so that the ray never bounces at a corner of the square.

Output

Output a single line with four space-separated integers $p$, $q$, $s$ and $t$, where $(p/q, s/t)$ is the final point where the ray hits a side of the square, $p/q$ and $s/t$ are in reduced form, and the denominators ($q$ and $t$) are positive. If one of the coordinates has value $0$, output it as 0 1.

The following is a picture of the first sample:

1 1 3

-1 1 0 1

1 7 4

-1 1 6 7

355 113 123456

1 1 -58 113