CF1196A.Three Piles of Candies

Alice and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.

After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.

Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).

You have to answer $q$ independent queries.

Let's see the following example: $[1, 3, 4]$. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has $4$ candies, and Bob has $4$ candies.

Another example is $[1, 10, 100]$. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes $54$ candies, and Alice takes $46$ candies. Now Bob has $55$ candies, and Alice has $56$ candies, so she has to discard one candy — and after that, she has $55$ candies too.

爱丽丝和鲍勃收到了三堆数量庞大的糖果作为礼物。现在他们希望尽可能公平地分配这些糖果。为此，爱丽丝先选择其中一堆糖果，然后鲍勃从剩下的两堆中选择一堆。最后一堆则由爱丽丝和鲍勃按各自意愿分配：例如，爱丽丝可以拿走整堆，而鲍勃一分不得。

在从各堆中取走糖果后，如果爱丽丝拥有的糖果数多于鲍勃，则她会丢弃一部分糖果，使得她剩余的糖果数等于鲍勃的糖果数；当然，若鲍勃的糖果更多，他也会做同样的操作。

爱丽丝和鲍勃希望最终各自拥有的糖果数量尽可能多，因此他们会精心规划整个分配过程。请计算经过该分配过程后，爱丽丝最多能拥有多少颗糖果（此时鲍勃也将拥有相同数量的糖果）。

你需要回答 $q$ 个相互独立的查询。

我们来看如下示例：$[1, 3, 4]$。此时爱丽丝可选择第三堆（含 $4$ 颗糖果），鲍勃选择第二堆（含 $3$ 颗糖果），第一堆仅剩的 $1$ 颗糖果全部归鲍勃——于是爱丽丝有 $4$ 颗糖果，鲍勃有 $4$ 颗糖果。

另一个例子是 $[1, 10, 100]$。此时爱丽丝可选择第二堆（含 $10$ 颗糖果），鲍勃选择第一堆（含 $1$ 颗糖果），第三堆的 $100$ 颗糖果可如此分配：鲍勃取 $54$ 颗，爱丽丝取 $46$ 颗。此时鲍勃共有 $1 + 54 = 55$ 颗糖果，爱丽丝共有 $10 + 46 = 56$ 颗糖果，因此爱丽丝需丢弃 $1$ 颗糖果——丢弃后，她也剩下 $55$ 颗糖果。

The first line of the input contains one integer $q$ ($1 \le q \le 1000$) — the number of queries. Then $q$ queries follow.

The only line of the query contains three integers $a, b$ and $c$ ($1 \le a, b, c \le 10^{16}$) — the number of candies in the first, second and third piles correspondingly.

输入的第一行包含一个整数 $q$（$1 \le q \le 1000$），表示查询次数。随后是 $q$ 个查询。

每个查询仅有一行，包含三个整数 $a, b$ 和 $c$（$1 \le a, b, c \le 10^{16}$），分别表示第一堆、第二堆和第三堆糖果的数量。

Print $q$ lines. The $i$-th line should contain the answer for the $i$-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).

输出 $q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案——即在 Alice 和 Bob 均采取最优策略的前提下，Alice 在分配后所能获得的最多糖果数（此时 Bob 所获得的糖果数与 Alice 相同）。