Frog Jumping_牛客博客

https://codeforces.com/contest/1077/problem/A

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A frog is currently at the point 0 on a coordinate axis Ox. It jumps by the following algorithm: the first jump is aa units to the right, the second jump is b units to the left, the third jump is a units to the right, the fourth jump is b units to the left, and so on.

Formally:

if the frog has jumped an even number of times (before the current jump), it jumps from its current position xx to position x+a;
otherwise it jumps from its current position xx to position x−b.

Your task is to calculate the position of the frog after kk jumps.

But... One more thing. You are watching tt different frogs so you have to answer tt independent queries.

Input

The first line of the input contains one integer tt (1≤t≤1000) — the number of queries.

Each of the next t lines contain queries (one query per line).

The query is described as three space-separated integers a,b,k (1≤a,b,k≤109) — the lengths of two types of jumps and the number of jumps, respectively.

Output

Print tt integers. The ii-th integer should be the answer for the i-th query.

Example

input

6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999

output

Note

In the first query frog jumps 5 to the right, 2 to the left and 5 to the right so the answer is 5−2+5=8.

In the second query frog jumps 100 to the right, 1 to the left, 100 to the right and 1 to the left so the answer is 100−1+100−1=198.

In the third query the answer is 1−10+1−10+1=−17.

In the fourth query the answer is 109−1+109−1+109−1=2999999997.

In the fifth query all frog's jumps are neutralized by each other so the answer is 0.

The sixth query is the same as the fifth but without the last jump so the answer is 1.

C++版本一

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
int t;
ll a,b,k;
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%I64d%I64d%I64d",&a,&b,&k);
        if(k%2==0)
            cout << (a-b)*k/2 << endl;
        else
            cout << (a-b)*(k/2)+a << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

With each pair of jumps of kind "to the right — to the left" the frog jumps a−b. So the answer is almost (a−b)⋅⌊k2⌋. Almost because there can be one more jump to the right. So if k is odd then we have to add a to the answer.

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int a, b, k;
		cin >> a >> b >> k;
		cout << (a - b) * 1ll * (k / 2) + a * (k & 1) << endl;
	}
	
	return 0;
}