Diagonal Walking v.2

CodeForces - 1036B

Mikhail walks on a Cartesian plane. He starts at the point (0,0)(0,0), and in one move he can go to any of eight adjacent points. For example, if Mikhail is currently at the point (0,0)(0,0), he can go to any of the following points in one move:

  • (1,0)(1,0);
  • (1,1)(1,1);
  • (0,1)(0,1);
  • (−1,1)(−1,1);
  • (−1,0)(−1,0);
  • (−1,−1)(−1,−1);
  • (0,−1)(0,−1);
  • (1,−1)(1,−1).

If Mikhail goes from the point (x1,y1)(x1,y1) to the point (x2,y2)(x2,y2) in one move, and x1≠x2x1≠x2 and y1≠y2y1≠y2, then such a move is called a diagonal move.

Mikhail has qq queries. For the ii-th query Mikhail's target is to go to the point (ni,mi)(ni,mi) from the point (0,0)(0,0) in exactly kiki moves. Among all possible movements he want to choose one with the maximum number of diagonal moves. Your task is to find the maximum number of diagonal moves or find that it is impossible to go from the point (0,0)(0,0) to the point (ni,mi)(ni,mi) in kiki moves.

Note that Mikhail can visit any point any number of times (even the destination point!).

Input

The first line of the input contains one integer qq (1≤q≤1041≤q≤104) — the number of queries.

Then qq lines follow. The ii-th of these qq lines contains three integers nini, mimi and kiki (1≤ni,mi,ki≤10181≤ni,mi,ki≤1018) — xx-coordinate of the destination point of the query, yy-coordinate of the destination point of the query and the number of moves in the query, correspondingly.

Output

Print qq integers. The ii-th integer should be equal to -1 if Mikhail cannot go from the point (0,0)(0,0) to the point (ni,mi)(ni,mi) in exactly kiki moves described above. Otherwise the ii-th integer should be equal to the the maximum number of diagonal moves among all possible movements.

Example

Input

32 2 34 3 710 1 9

Output

16-1

Note

One of the possible answers to the first test case: (0,0)→(1,0)→(1,1)→(2,2)(0,0)→(1,0)→(1,1)→(2,2).

One of the possible answers to the second test case: (0,0)→(0,1)→(1,2)→(0,3)→(1,4)→(2,3)→(3,2)→(4,3)(0,0)→(0,1)→(1,2)→(0,3)→(1,4)→(2,3)→(3,2)→(4,3).

In the third test case Mikhail cannot reach the point (10,1)(10,1) in 9 moves.

题意：

为了防止比赛被ak！为了守护世界的和平！我们！贯彻爱与真实的险恶！恩爱又迷人的出题组！！决定！！！把zzq抓起来，放到一个荒无人烟岛上。zzq所在的位置是（0,0），而离开荒岛的传送阵在（n,m），zzq的体力值只够他走k步，zzq每次可以走8个方向。
（1,0)
(1,1)
(0,1)
(−1,1)
(−1,0)
(−1,−1)
(0,−1)
(1,−1)
但是温柔善良的大魔王SYH怎么会让zzq轻易的逃离荒岛，所以她希望zzq尽量多地往斜方向走，传送阵仅在第k秒开启，口令就是zzq最多可以往斜方向走的步数。
可怜的zzq被土拨鼠吸走了所有的脑细胞，于是他打电话给你想让你帮他解出口令。

思路：

如果 x > y 先swap（x，y），交换xy并不影响答案。

然后 先从（ 0 ，0 ）走到（x，x）

然后再竖直向上走，

我们令z=k-x，

如果剩下的路程 y=（y-x）

那么接下来

如果y和z都是奇数，用z中的一个1，走y中的一个单位。

两者都变成偶数，而偶数可以通过这样的走法使剩下的全部z都走歇着的。

否则如果y和z中只有一个是奇数，用z中的偶数部分去全走斜的，答案再必须减去1.

细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int* p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int q;
ll x, y, k;
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%lld %lld %lld", &x, &y, &k);
        if (x > y)
        {
            swap(x, y);
        }
        ll z = k - x;
        y -= x;
        if (z < y)
        {
            printf("-1\n");
        } else
        {
            if (z & 1)
                x += z - 1;
            else
                x += z;
            if (y & 1)
            {
                y = 1;
            } else
            {
                y = 0;
            }
            if (z & 1)
            {
                z = 1;
            } else
            {
                z = 0;
            }
            if (z & y)
            {

            } else if (z + y)
            {
                x--;
            }
            printf("%lld\n", x );
        }
    }



    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}