Round #512 (Div. 2) 1030D - Vasya and Triangle

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 nn, mm and kk. He'd like to find three integer points (x1,y1)(x1,y1), (x2,y2)(x2,y2), (x3,y3)(x3,y3), such that 0≤x1,x2,x3≤n0≤x1,x2,x3≤n, 0≤y1,y2,y3≤m0≤y1,y2,y3≤m and the area of the triangle formed by these points is equal to nmknmk.

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 nn, mm, kk (1≤n,m≤1091≤n,m≤109, 2≤k≤1092≤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,yixi,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

input

Copy

4 4 7

output

Copy

NO

Note

In the first example area of the triangle should be equal to nmk=4nmk=4. The triangle mentioned in the output is pictured below:

Round #512 (Div. 2) 1030D - Vasya and Triangle

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

Doubled area of any triangle with integer coordinates is always integer. That's why if 2nm2nm is not divisible by kk then there is no valid triangle.

Otherwise, it's always possible to find required triangle. We will construct the answer with next algorithm. At first, if kk is even then divide it by 22. Next, find g=gcd(k,n)g=gcd(k,n), where gcd(x,y)gcd(x,y) is greatest common divisor of xx and yy. Denote k′=kgk′=kg and assign a=nga=ng as length of the first side. Next assign b=mk′b=mk′ as length of the second side. Now, if kk was odd we need to multiply one of the sides by 22. If a<na<n then a=2aa=2a, otherwise b=2bb=2b. bb still won't be greater than mm since if a=na=n then bb was strictly lower than mm.

The answer is the triangle with vertices (0,0),(a,0),(0,b)(0,0),(a,0),(0,b). You can check that its area is equal to nmknmk.

上面一段是题解。三角形的面积乘2一定是整数，所以2nm/k一定是整数。然后根据这个公式 Round #512 (Div. 2) 1030D - Vasya and Triangle

x1y2-x2y1=2nm/k。让两个点在边上：x1y2 = 2nm/k。再分解一下就行。

#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 50010
#define M 2000100
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

ll n, m, k, a;

ll gcd(ll a, ll b)
{
    ll tmp;
    while(b) {
        tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
    #endif

    cin >> n >> m >> k;
    a = 2 * n * m / k;

    if(2 * n * m % k == 0) {
        puts("YES");
        ll a, b, g;
        if(k & 1) {
            g = gcd(n, k);
            a = n / g;
            k /= g;
            b = m / k;
            if(a * 2 < n) a *= 2;
            else b *= 2;
        }
        else {
            k /= 2;
            g = gcd(n, k);
            a = n / g;
            k /= g;
            b = m / k;
        }

        puts("0 0");
        printf("%I64d 0\n", a);
        printf("0 %I64d\n", b);
    }
    else {
        puts("NO");
    }

    return 0;
}

Round #512 (Div. 2) 1030D - Vasya and Triangle

相关推荐