D. Vasya and Triangle（数学思维）

en .感觉学弟都过了。我也没想出来。只想到了开始，没有想到怎么凑，感觉挺可惜的。

http://codeforces.com/problemset/problem/1058/D

D. Vasya and Triangle

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vasya has got three integers n

, m and k. He'd like to find three integer points (x1,y1), (x2,y2), (x3,y3), such that 0≤x1,x2,x3≤n, 0≤y1,y2,y3≤m and the area of the triangle formed by these points is equal to nmk

.

Help Vasya! Find such points (if it's possible). If there are multiple solutions, print any of them.

Input

The single line contains three integers n

, m, k (1≤n,m≤109, 2≤k≤109

).

Output

If there are no such points, print "NO".

Otherwise print "YES" in the first line. The next three lines should contain integers xi,yi

— coordinates of the points, one point per line. If there are multiple solutions, print any of them.

You can print each letter in any case (upper or lower).

Examples

Input

Copy

4 3 3

Output

Copy

YES 1 0 2 3 4 1

Input

Copy

4 4 7

Output

Copy

NO

Note

In the first example area of the triangle should be equal to nmk=4

. The triangle mentioned in the output is pictured below:

In the second example there is no triangle with area nmk=167

思路

显然，不论最终找到的三角形处于什么形态，我们都可以通过平移旋转将其一个顶点设置为原点，且满足三角形位于矩形内部。

我们设这三点分别为 A(0,0),B(x1,y1),C(x2,y2)，由此得到两条向量，根据叉乘求得三角形面积为 |x1y2−x2y1|2。

于是我们只需要找到合适的两个点使得 |x1y2−x2y1|=2nmk即可。

左端必为整数，因此假若 2nm%k≠0

，则无解，对于其他情况必有解存在。

我们假设 B,C两点都位于坐标轴，即 x2=y1=0，|x1y2−x2y1|=x1y2，相当于我们只需将 2nmk分解为两个满足题意的整数乘积即可。

因为 2nm%k=0，则 2nm 必包含 k 所有的素因子，求得 u=gcd(2n,k)

若 u=1，显然 m 可以整除 k，令 x1=n,y2=2×m/k即可；

否则令 x1=2×n/u,y2=m×u/k即可。

代码：

#include <bits/stdc++.h> #define IO \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); using namespace std; typedef long long LL; const int maxn = 1e5 + 10; LL n, m, k; bool solve() { if (2LL * n * m % k != 0) return false; cout << "YES" << endl; LL a, b, gc = __gcd(2LL * n, k); if (gc == 1) b = 2LL * m / k, a = n; else a = 2LL * n / gc, b = m * gc / k; cout << "0 0" << endl; cout << 0 << " " << b << endl; cout << a << " " << 0 << endl; return true; } int main() { #ifdef LOCAL_IM0QIANQIAN freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); #else IO; #endif // LOCAL_IM0QIANQIAN cin >> n >> m >> k; if (!solve()) { cout << "NO" << endl; } return 0; }