Михаил ходит по декартовой плоскости. Он начинает в точке \((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\) целых чисел. \(i\)-е число должно быть равно -1, если Михаил не может дойти из точки \((0, 0)\) в точку \((n_i, m_i)\) ровно за \(k_i\) ходов, описанных выше. Иначе \(i\)-е число должно быть равно максимальному количеству диагональных ходов среди всех возможных способов дойти.
Примечание
Один из возможных ответов на первый тестовый пример: \((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 ходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2 3
4 3 7
10 1 9
|
1
6
-1
|