Марсианские ученые исследуют Ганимед, один из многочисленных спутников Юпитера. Недавно на нем были обнаружены руины древней цивилизации. Ученые доставили на Марс несколько табличек с надписями на неизвестном науке языке.
Было установлено, что жители Ганимеда использовали алфавит из двух букв, причем каждое слово имело фиксированную длину — ровно \(\ell\) букв. Поэтому ученые решили записывать каждое слово этого языка как целое положительное число от \(0\) до \(2^{\ell} - 1\). Первой букве алфавита соответствуют нули в двоичной записи числа, а второй букве алфавита — единицы.
Одно и то же слово может иметь в языке разные формы. Тогда необходимо восстановить начальную форму слова. Ниже описано, как это делается.
Назовем расстоянием между двумя словами количество позиций, в которых эти слова различаются. Например, расстояние между словами \(1001_2\) и \(1100_2\) (в двоичной записи) равно двум, т. к. они имеют разные буквы на второй и четвертой позициях, если считать слева направо. Будем в дальнейшем обозначать расстояние между словами \(x\) и \(y\) как \(d(x, y)\).
Пусть слово имеет \(n\) форм, \(i\)-я из которых описывается целым числом \(x_i\). Все \(x_i\) не обязательно различны, т. к. две разные формы слова могут записываться одинаково. Рассмотрим некоторое слово \(y\). Тогда близость слова \(y\) равна сумме расстояний до каждой из форм исследуемого слова, т. е. сумме \(d(x_i, y)\) по всем \(1 \le i \le n\).
Начальной формой является слово \(y\) с минимально возможной близостью.
Вам необходимо помочь ученым и написать программу, которая находит начальную форму слова по всем его известным формам. Обратите внимание, что начальная форма не обязательно должна совпадать с какой-либо из известных \(n\) форм слова.
Выходные данные
Для каждого теста выведите одно целое число — начальную форму слова, т. е. такое \(y\) (\(0 \le y \le 2^\ell - 1\)), что сумма \(d(x_i, y)\) по всем \(1 \le i \le n\) минимально возможная. Обратите внимание, что \(y\) не обязано совпадать с каким-либо числом из \(x_i\).
Если вариантов восстановить начальную форму слова несколько, выведите любой из них.
Примечание
Рассмотрим примеры из условия.
В первом примере слова в двоичной записи записываются как \(x_1 = 10010_2\), \(x_2 = 01001_2\) и \(x_3 = 10101_2\). Пусть \(y = 10001_2\). Тогда \(d(x_1, y) = 2\) (различие в четвертой и пятой позиции), \(d(x_2, y) = 2\) (различие в первой и второй позиции), \(d(x_3, y) = 1\) (различие в третьей позиции). Получаем, что близость равна \(2 + 2 + 1 = 5\). Можно показать, что меньшего значения близости добиться невозможно.
Во втором примере все формы слова одинаковы и равны \(18\) (\(10010_2\) в двоичной записи), поэтому начальная форма тоже равна \(18\). Как нетрудно догадаться, близость в таком случае равна нулю.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 5
18 9 21
3 5
18 18 18
1 1
1
5 30
1 2 3 4 5
6 10
99 35 85 46 78 55
2 1
0 1
8 8
5 16 42 15 83 65 78 42
|
17
18
1
1
39
0
2
|