시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 (추가 시간 없음) 1024 MB127758.333%

문제

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.

입력

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 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.

예제 입력 1

1 1 3

예제 출력 1

-1 1 0 1

예제 입력 2

1 7 4

예제 출력 2

-1 1 6 7

예제 입력 3

355 113 123456

예제 출력 3

1 1 -58 113

힌트

The following is a picture of the first sample: