B. Ходьба по диагонали v.2
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Михаил ходит по декартовой плоскости. Он начинает в точке $$$(0, 0)$$$, и за один ход он может перейти в любую из восьми соседних точек. Например, если сейчас Михаил находится в точке $$$(0, 0)$$$, он может пойти в точки:

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

Если Михаил идет из точки $$$(x1, y1)$$$ в точку $$$(x2, y2)$$$ за один ход, и $$$x1 \ne x2$$$ и $$$y1 \ne y2$$$, то такой ход называется диагональным ходом.

У Михаила есть $$$q$$$ запросов. В $$$i$$$-м запросе целью Михаила является дойти до точки $$$(n_i, m_i)$$$ из точки $$$(0, 0)$$$ ровно за $$$k_i$$$ ходов. Среди всех возможных способов дойти он хочет выбрать такой, в котором максимальное количество диагональных ходов. Ваша задача — найти максимальное количество диагональных ходов или сказать, что добраться из точки $$$(0, 0)$$$ до точки $$$(n_i, m_i)$$$ за $$$k_i$$$ ходов невозможно.

Заметьте, что Михаил может посещать любую точку любое количество раз (даже точку назначения!).

Входные данные

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^4$$$) — количество запросов.

Далее следуют $$$q$$$ строк. $$$i$$$-я из $$$q$$$ строк содержит три целых числа $$$n_i$$$, $$$m_i$$$ и $$$k_i$$$ ($$$1 \le n_i, m_i, k_i \le 10^{18}$$$) — $$$x$$$-координата точки назначения запроса, $$$y$$$-координата точки назначения запроса и количество ходов в запросе соответственно.

Выходные данные

Выведите $$$q$$$ целых чисел. $$$i$$$-е число должно быть равно -1, если Михаил не может дойти из точки $$$(0, 0)$$$ в точку $$$(n_i, m_i)$$$ ровно за $$$k_i$$$ ходов, описанных выше. Иначе $$$i$$$-е число должно быть равно максимальному количеству диагональных ходов среди всех возможных способов дойти.

Пример
Входные данные
3
2 2 3
4 3 7
10 1 9
Выходные данные
1
6
-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)$$$.

В третьем тестовом примере Михаил не может достичь точку $$$(10, 1)$$$ за 9 ходов.