정사각형에서의 반사

좌표평면에서 네 꼭짓점이 $(-1,-1)$, $(-1,1)$, $(1,1)$, $(1,-1)$인 정사각형이 있다. 점 $(-1,0)$에서 정사각형 내부로 주어진 기울기의 경로를 따라 광선을 쏜다. 광선은 정사각형의 변에 부딪히면, 교점에서 변에 대한 입사각과 같은 반사각으로 반사된다.

여러 번 반사된 뒤, 광선은 정사각형의 변 중 하나와 유리수 좌표를 갖는 점에서 다시 만난다. 그 유리수 좌표를 기약분수로 구하라.

입력은 한 줄로 주어지며, 세 정수 $a$, $b$, $n$이 포함된다 ($1 \le a,b,n \le 10^6$, $\gcd(a,b)=1$). 광선의 처음 경로의 기울기는 $a/b$이고, 반사 횟수는 $n$이다. $a$와 $b$는 서로소이다. 기울기는 광선이 정사각형의 꼭짓점에서 반사되지 않도록 주어진다.

광선이 정사각형의 변에 마지막으로 닿는 점이 $(p/q, s/t)$일 때, 공백으로 구분된 네 정수 $p$, $q$, $s$, $t$를 한 줄에 출력한다. $p/q$와 $s/t$는 기약분수이고 분모 $q$와 $t$는 양수이다. 어느 좌표의 값이 $0$이면 0 1로 출력한다.

다음은 첫 번째 예제를 나타낸 그림이다: