Поскольку Гриша весь год вел себя хорошо, в новогоднюю ночь его посетил Дед Мороз с мешком подарков! В мешке Деда Мороза содержатся n сладких конфет из той самой кондитерской, по одной конфете каждой возможной вкусности от 1 до n.
Счастье Гриши напрямую зависит от того, какие именно конфеты он возьмет. Несмотря на то, что разумно предположить, что брать нужно наиболее вкусные конфеты, новогодняя магия переворачивает все с ног на голову: оказывается, важна не просто сумма вкусностей конфет, а их XOR-сумма!
XOR-сумма последовательности целых чисел a1, a2, ..., am считается как побитовый XOR всех элементов последовательности: 
, здесь 
обозначает операцию побитового XOR; подробнее про побитовый XOR (операцию, также известную как побитовое исключающее ИЛИ) можно прочитать здесь.
Дед Мороз заранее предупредил Гришу, что ему требуется посетить еще несколько мест, а потому Гриша волен выбрать не более k конфет из мешка Деда Мороза. Помогите Грише узнать, чему равна максимальная XOR-сумма, а вместе с ней и максимальное счастье, которое он может обрести при оптимальном выборе конфет.
Примечание
В первом примере можно взять конфеты со вкусностями 1, 2 и 4. Их XOR-сумма равняется 7.
Во втором примере можно взять все шесть конфет и получить XOR-сумму 7.