补充最少的奖品

题目描述

现有 a 件第一类奖品和 b 件第二类奖品。选择礼包数 d，满足 2≤d≤K；允许分别补充若干件奖品，使补充后的两类总数都能被 d 整除。首先使两类补充数量之和最小；若多个 d 并列，选择其中较大的 d。

输入格式

一行输入三个整数 a、b、K，满足 1≤a,b≤10^9、2≤K≤10^6。

输出格式

第一行输出按规则选中的礼包数 d。第二行输出第一类和第二类奖品分别需要补充的最少数量，顺序与 a、b 对应。

样例

输入

23 35 10

输出

6
1 1