You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

连分数是一种特别的分数，通过辗转相除法得到分母（商），分子都是1，取前k项连分数的值，就得到相似度为k的分数，我们叫它“土拨鼠分数”，比如355/113≈22/7 算法为 a/(b+c/d)=ad/bc+d

题目要求

输入分子和分母，输出近似分数

输入

第一行两个整数m,n，分别是分子和分母 第二行为近似度k，$1<=m<=n<=10000，1<=k$

输出

两个数

样例

314159265 100000000
4

355 113