[CF1030D] Vasya and Triangle

Vasya and Triangle

翻译:

Vasya有三个数n,m,k。他想要找到三个整点(x1,y1),(x2,y2),(x3,y3)满足0≤x1,x2,x3≤n,0≤y1,y2,y3≤m并且由这三点组成的三角形面积等于nm/k。

帮助Vasya找到这样的点(如果可能的话)。如果有多组解,输出任意一组即可。

Input

仅一行,包括三个整数n,m,k(1≤n,m≤10^9,2≤k≤10^9)。

Output

如果没有这样的点,输出"NO"。

否则在第一行输出"YES"。接下来三行每行包括两个整数xi,yi,代表点的坐标。如果有多组解,输出任意一组即可。

你可以任意输出大写或小写的英文字母。

Note

在第一组样例中三角形的面积等于nm/k=4。这个三角形的图示在下方。

在第二组样例中不存在三角形的面积满足nm/k=16/7。

Tutorial

将任意坐标都是整点的三角形面积加倍总会得到一个整数。这就是如果2nm不能被k整除,就没有合法的三角形的原因。

反之,总是存在满足条件的三角形。我们将会在接下来的算法里构造答案。首先,如果k是偶数那么就将它除2。接着,令g = gcd(k, n),在这里gcd(x, y)代表x和y的最大公约数。取k' = k / g,令 a = n / g 并使其作为三角形的一边长。然后令b = m / k'作为三角形的另一边长。现在,如果k是奇数我们应将其中一边长乘以2。如果a < n那么令a = 2a,否则就令b = 2b。b不会大于m,因为假如a=n那么b是严格小于m的。

答案就是由顶点(0, 0), (a, 0), (0, b)构成的三角形。你可以检查它的面积是否等于nm/k。

继续阅读[CF1030D] Vasya and Triangle