CF1036B.Diagonal Walking v.2

Mikhail walks on a Cartesian plane. He starts at the point $(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)$, he can go to any of the following points in one move:

• $(1, 0)$;
• $(1, 1)$;
• $(0, 1)$;
• $(-1, 1)$;
• $(-1, 0)$;
• $(-1, -1)$;
• $(0, -1)$;
• $(1, -1)$.

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

Mikhail has $q$ queries. For the $i$-th query Mikhail's target is to go to the point $(n_i, m_i)$ from the point $(0, 0)$ in exactly $k_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)$ to the point $(n_i, m_i)$ in $k_i$ moves.

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

米哈伊尔在笛卡尔平面上行走。他从点 $(0, 0)$ 出发，每次移动可以到达八个相邻点中的任意一个。例如，若米哈伊尔当前位于点 $(0, 0)$，则他一次移动可到达以下任意一点：

• $(1, 0)$；
• $(1, 1)$；
• $(0, 1)$；
• $(-1, 1)$；
• $(-1, 0)$；
• $(-1, -1)$；
• $(0, -1)$；
• $(1, -1)$。

若米哈伊尔从点 $(x_1, y_1)$ 一次移动到点 $(x_2, y_2)$，且满足 $x_1 \ne x_2$ 且 $y_1 \ne y_2$，则称该移动为对角线移动。

米哈伊尔共有 $q$ 个查询。对于第 $i$ 个查询，他的目标是在恰好 $k_i$ 步内从点 $(0, 0)$ 到达点 $(n_i, m_i)$。在所有可行的路径中，他希望选择对角线移动次数最多的那一条。你的任务是求出该最大对角线移动次数；若无法在 $k_i$ 步内从 $(0, 0)$ 到达 $(n_i, m_i)$，则判定为不可能。

注意：米哈伊尔可以多次访问任意点（包括终点！）。

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

Then $q$ lines follow. The $i$-th of these $q$ lines contains three integers $n_i$, $m_i$ and $k_i$ ($1 \le n_i, m_i, k_i \le 10^{18}$) — $x$-coordinate of the destination point of the query, $y$-coordinate of the destination point of the query and the number of moves in the query, correspondingly.

输入的第一行包含一个整数 $q$（$1 \le q \le 10^4$），表示查询次数。

接下来是 $q$ 行。其中第 $i$ 行包含三个整数 $n_i$、$m_i$ 和 $k_i$（$1 \le n_i, m_i, k_i \le 10^{18}$），分别表示第 $i$ 次查询中目标点的 $x$ 坐标、$y$ 坐标以及该次查询的移动步数。

Print $q$ integers. The $i$-th integer should be equal to -1 if Mikhail cannot go from the point $(0, 0)$ to the point $(n_i, m_i)$ in exactly $k_i$ moves described above. Otherwise the $i$-th integer should be equal to the the maximum number of diagonal moves among all possible movements.

输出 $q$ 个整数。其中第 $i$ 个整数应为 $-1$，如果 Mikhail 无法在上述描述的恰好 $k_i$ 步内从点 $(0, 0)$ 到达点 $(n_i, m_i)$；否则，第 $i$ 个整数应为所有可行路径中对角线移动次数的最大值。

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

One of the possible answers to the second test case: $(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)$ in 9 moves.

第一个测试用例的一种可能答案：$(0, 0) \to (1, 0) \to (1, 1) \to (2, 2)$。

第二个测试用例的一种可能答案：$(0, 0) \to (0, 1) \to (1, 2) \to (0, 3) \to (1, 4) \to (2, 3) \to (3, 2) \to (4, 3)$。

在第三个测试用例中，Mikhail 无法在 9 步内到达点 $(10, 1)$。