Алиса и Боб получили три большие кучки конфет в качестве подарка. Теперь они хотят разделить эти конфеты между собой настолько честно, насколько это возможно. Чтобы сделать это, Алиса забирает одну кучку с конфетами себе, затем Боб забирает одну из других двух кучек себе. Последняя кучка делится между Алисой и Бобом так, как они хотят: например, возможно, что Алиса возьмет всю кучку себе, а Боб не получит из нее ничего.
После того как они возьмут все конфеты из кучек, если у Алисы будет больше конфет, чем у Боба, она выкидывает некоторые конфеты таким образом, что количество ее конфет становится равным количеству конфет Боба. Конечно, Боб сделает то же самое, если у него больше конфет.
Алиса и Боб хотят иметь как можно больше конфет каждый, и будут планировать процесс разделения конфет соответственно. Пожалуйста, посчитайте максимально возможное количество конфет, которое может оказаться у Алисы после процесса их разделения (конечно же, у Боба будет столько же конфет).
Вам необходимо ответить на \(q\) независимых запросов.
Рассмотрим следующий пример: \([1, 3, 4]\). Здесь Алиса может взять третью кучку, Боб может взять вторую кучу, и единственную оставшуюся конфету из первой кучки получает Боб — тогда у Алисы будет \(4\) конфеты и у Боба тоже будет \(4\) конфеты.
Другой возможный пример — это \([1, 10, 100]\). Тогда Алиса может выбрать вторую кучку, Боб может выбрать первую кучку, и конфеты из третьей кучки могут быть разделены таким образом, что Боб получит \(54\) конфеты, а Алиса получит \(46\) конфет. Теперь у Боба есть \(55\) конфет, а у Алисы — \(56\) конфет, таким образом, она должна выкинуть одну конфету — и после этого у нее будет также \(55\) конфет.
Выходные данные
Выведите \(q\) строк. \(i\)-я строка должна содержать ответ на \(i\)-й запрос — максимальное количество конфет, которое Алиса может иметь после разделения, если и Алиса, и Боб будут действовать оптимально (конечно же, Боб будет иметь такое же количество конфет).