Готтфрид узнал про двоичное представление чисел. Он придумал эту задачу и предложил её вам.
Вам дан набор из \(n\) неотрицательных целых чисел \(a_1, \ldots, a_n\). Вы можете выполнять следующую операцию: выбрать два различных индекса \(1 \leq i, j \leq n\). Если перед операцией \(a_i = x\), \(a_j = y\), то после операции \(a_i = x~\mathsf{AND}~y\), \(a_j = x~\mathsf{OR}~y\), где \(\mathsf{AND}\) и \(\mathsf{OR}\) — операции побитового И и ИЛИ соответственно (для формального описания см. раздел Комментарии). Данную операцию можно применять любое количество раз (возможно, ноль).
После того, как все операции выполнены, вычислим \(\sum_{i=1}^n a_i^2\) — сумму квадратов всех \(a_i\). Какую максимальную сумму квадратов можно получить?
Выходные данные
Выведите одно число — максимально возможная сумма квадратов после применения нескольких операций (возможно, ни одной).
Примечание
В первом примере нельзя сделать ни одной операции, поэтому ответ равен \(123^2\).
Во втором примере мы можем получить набор \(1, 1, 7\), и \(1^2 + 1^2 + 7^2 = 51\).
Если \(x\) и \(y\) записаны в двоичной системе с одинаковым числом бит (возможно, с ведущими нулями), то любой бит \(x~\mathsf{AND}~y\) равен \(1\) тогда и только тогда, когда оба соответствующих бита \(x\) и \(y\) равны \(1\). Аналогично, любой бит \(x~\mathsf{OR}~y\) равен \(1\) тогда и только тогда, когда хотя бы один из соответствующих битов \(x\) и \(y\) равен \(1\). Например, \(x = 3\) и \(y = 5\) можно представить как \(011_2\) и \(101_2\) (старший бит слева). Тогда \(x~\mathsf{AND}~y = 001_2 = 1\) и \(x~\mathsf{OR}~y = 111_2 = 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
123
|
15129
|
|
2
|
3
1 3 5
|
51
|
|
3
|
2
349525 699050
|
1099509530625
|