CF1036B Diagonal Walking v.2

Mikhail 在笛卡尔平面上行走。他从点 $(0, 0)$ 出发，每一步可以走到任意一个相邻的八个点。例如，如果 Mikhail 当前在点 $(0, 0)$，他可以在一步内走到以下任意一个点： - $(1, 0)$； - $(1, 1)$； - $(0, 1)$； - $(-1, 1)$； - $(-1, 0)$； - $(-1, -1)$； - $(0, -1)$； - $(1, -1)$。 如果 Mikhail 从点 $(x_1, y_1)$ 走到点 $(x_2, y_2)$，且 $x_1 \ne x_2$ 且 $y_1 \ne y_2$，那么这一步被称为“对角线移动”。 Mikhail 有 $q$ 个询问。对于第 $i$ 个询问，Mikhail 的目标是用恰好 $k_i$ 步从点 $(0, 0)$ 走到点 $(n_i, m_i)$。在所有可能的移动方式中，他希望选择对角线移动次数最多的一种。你的任务是求出最多能进行多少次对角线移动，或者判断是否无法用 $k_i$ 步从 $(0, 0)$ 走到 $(n_i, m_i)$。 注意，Mikhail 可以多次经过任意点（包括终点）。

输入的第一行包含一个整数 $q$（$1 \le q \le 10^4$），表示询问的数量。 接下来有 $q$ 行，每行包含三个整数 $n_i$、$m_i$ 和 $k_i$（$1 \le n_i, m_i, k_i \le 10^{18}$），分别表示第 $i$ 个询问的目标点的 $x$ 坐标、$y$ 坐标和步数。

输出 $q$ 个整数。第 $i$ 个整数表示如果无法用 $k_i$ 步从 $(0, 0)$ 走到 $(n_i, m_i)$，则输出 $-1$；否则输出在所有可能的移动方式中最多的对角线移动次数。

第一个测试用例的一种可能答案：$(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)$。 由 ChatGPT 4.1 翻译