Alice 和 Bob 收到了三大堆糖果作为礼物。现在他们想尽可能公平地分配这些糖果。为此,爱丽丝拿走一堆糖果,然后鲍勃拿走另外两堆糖果之一。最后一堆按照 Alice 和 Bob 的意愿分配:例如,Alice 可能拿走整堆,而 Bob 却什么也得不到。
从糖果堆中取出糖果后,如果 Alice 的糖果比 Bob 多,她会丢弃一些糖果,这样她拥有的糖果数量就等于 Bob 拥有的糖果数量。当然,如果鲍勃有更多糖果,他也会这样做。
Alice和Bob想要拥有尽可能多的糖果,他们相应地规划了分配糖果的过程。请计算出经过此划分过程后,Alice 最多可以拥有多少颗糖果(当然,Bob 也将拥有相同数量的糖果)。
您必须回答 $$$q$$$ 独立查询。
让我们看以下示例:$$$[1, 3, 4]$$$。然后爱丽丝可以选择第三堆,鲍勃可以拿第二堆,然后第一堆中唯一的糖果给鲍勃 - 那么爱丽丝有 $$$4$$$ 糖果,鲍勃有 $$$4$$$ 糖果。
另一个例子是$$$[1, 10, 100]$$$。那么Alice可以选择第二堆,Bob可以选择第一堆,第三堆糖果可以这样分配:Bob拿走$$$54$$$糖果,Alice拿走$$$46$$$糖果。现在鲍勃有 $$$55$$$ 糖果,爱丽丝有 $$$56$$$ 糖果,所以她必须丢弃一颗糖果 - 之后,她也有 $$$55$$$ 糖果。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 1000$$$) — 查询数。然后是 $$$q$$$ 查询。
查询中唯一一行包含三个整数 $$$a、b$$$ 和 $$$c$$$ ($$$1 \le a, b, c \le 10^{16}$$$)——分别对应第一堆、第二堆和第三堆糖果的数量。
输出
打印 $$$q$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 查询的答案 - 如果爱丽丝和鲍勃都表现最佳,则爱丽丝在除法后可以拥有的最大糖果数量(当然,鲍勃将拥有相同数量的糖果)。
示例
输入 #1
4 1 3 4 1 10 100 10000000000000000 10000000000000000 10000000000000000 23 34 45
输出 #1
4 55 15000000000000000 51