CF1036B.Diagonal Walking v.2

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 x1x2x1 \ne x2 and y1y2y1 \ne 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)(n_i, m_i) from the point (0,0)(0, 0) in exactly kik_i 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)(n_i, m_i) in kik_i moves.

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

输入格式

The first line of the input contains one integer qq ( 1q1041 \le q \le 10^4 ) — the number of queries.

Then qq lines follow. The ii -th of these qq lines contains three integers nin_i , mim_i and kik_i ( 1ni,mi,ki10181 \le n_i, m_i, k_i \le 10^{18} ) — 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.

输出格式

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)(n_i, m_i) in exactly kik_i moves described above. Otherwise the ii -th integer should be equal to the the maximum number of diagonal moves among all possible movements.

输入输出样例

  • 输入#1

    3
    2 2 3
    4 3 7
    10 1 9
    

    输出#1

    1
    6
    -1
    

说明/提示

One of the possible answers to the first test case: (0,0)(1,0)(1,1)(2,2)(0, 0) \to (1, 0) \to (1, 1) \to (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) \to (0, 1) \to (1, 2) \to (0, 3) \to (1, 4) \to (2, 3) \to (3, 2) \to (4, 3) .

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

首页