Вам дан массив \(a\), состоящий из \(n\) различных элементов, и целое число \(k\). Каждый элемент в массиве это неотрицательное целое число, не превосходящее \(2^k-1\).
Обозначим через XOR расстояние для числа \(x\) следующую величину:
\(\)f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,\(\)
где через \(\oplus\) обозначено побитовое исключающее ИЛИ.
Для каждого целого числа \(x\) от \(0\) до \(2^k-1\) посчитайте \(f(x)\).
Выходные данные
Выведите \(2^k\) чисел. \(i\)-е из них должно равняться \(f(i-1)\).
Примечание
Рассмотрим первый пример:
- для \(x = 0\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([6, 0, 3]\), и минимальный модуль разности между элементами равен \(3\);
- для \(x = 1\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([7, 1, 2]\), и минимальный модуль разности между элементами равен \(1\);
- для \(x = 2\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([4, 2, 1]\), и минимальный модуль разности между элементами равен \(1\);
- для \(x = 3\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([5, 3, 0]\), и минимальный модуль разности между элементами равен \(2\);
- для \(x = 4\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([2, 4, 7]\), и минимальный модуль разности между элементами равен \(2\);
- для \(x = 5\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([3, 5, 6]\), и минимальный модуль разности между элементами равен \(1\);
- для \(x = 6\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([0, 6, 5]\), и минимальный модуль разности между элементами равен \(1\);
- для \(x = 7\), если мы применим XOR ко всем элементам массива с числом \(x\), мы получим массив \([1, 7, 4]\), и минимальный модуль разности между элементами равен \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
6 0 3
|
3 1 1 2 2 1 1 3
|
|
2
|
3 4
13 4 2
|
2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2
|