Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

A2. 15K4JR3B (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
— Вы знали, что если на карте соединить Парк культуры, одну точку не на северо-востоке и еще одну, то вы будете как дурак?

— Нет, я не знал, а это правда?

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии за одну операцию координата точки изменяется на степень двойки.

Безработный $$$\ast$$$ Ангел размещает три точки $$$A$$$, $$$B$$$ и $$$C$$$ в начале координат, а также дает вам массив $$$a$$$ длины $$$n$$$.

Вы должны выполнить ровно $$$n$$$ операций. Во время $$$i$$$-й операции выберите одну из этих точек и увеличьте или уменьшите одну из ее координат на $$$2^{a_i}$$$. Иначе говоря, если выбранная точка имеет координаты $$$(x, y)$$$, за $$$i$$$-ю операцию вы можете переместить ее в точку $$$(x + 2^{a_i}, y)$$$, $$$(x - 2^{a_i}, y)$$$, $$$(x, y + 2^{a_i})$$$ или $$$(x, y - 2^{a_i})$$$.

Безработный $$$\ast$$$ Ангел просит вас найти максимальную удвоенную площадь треугольника $$$ABC$$$ после выполнения всех операций. Так как она является вашим айдолом, вы не можете ей отказать.

Поскольку Безработный $$$\ast$$$ Ангел очень умна, она может показать, что интересующее ее значение всегда является целым числом.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — длину массива $$$a$$$ и количество операций.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 24$$$) — элементы массива $$$a$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальную удвоенную площадь треугольника $$$ABC$$$.

Пример
Входные данные
4
2
0 0
3
0 0 1
6
0 1 2 2 4 0
6
24 24 24 0 0 0
Выходные данные
1
4
192
562950054084608
Примечание

В первом наборе входных данных увеличим координату $$$x$$$ точки $$$B$$$ на $$$2^0$$$, затем увеличим координату $$$y$$$ точки $$$C$$$ на $$$2^0$$$. После этих $$$2$$$ операций точки имеют координаты $$$A = (0, 0)$$$, $$$B = (1, 0)$$$ и $$$C = (0, 1)$$$. Удвоенная площадь полученного треугольника равна $$$1$$$.

                  

Во втором наборе входных данных уменьшим координату $$$x$$$ точки $$$A$$$ на $$$2^0$$$, затем увеличим координату $$$x$$$ точки $$$B$$$ на $$$2^0$$$ и, наконец, увеличим координату $$$y$$$ точки $$$C$$$ на $$$2^1$$$. После этих $$$3$$$ операций точки имеют координаты $$$A = (-1, 0)$$$, $$$B = (1, 0)$$$ и $$$C = (0, 2)$$$. Удвоенная площадь полученного треугольника равна $$$4$$$.