Поскольку Гриша весь год вел себя хорошо, в новогоднюю ночь его посетил Дед Мороз с мешком подарков! В мешке Деда Мороза содержатся n сладких конфет из той самой кондитерской, по одной конфете каждой возможной вкусности от 1 до n.

Счастье Гриши напрямую зависит от того, какие именно конфеты он возьмет. Несмотря на то, что разумно предположить, что брать нужно наиболее вкусные конфеты, новогодняя магия переворачивает все с ног на голову: оказывается, важна не просто сумма вкусностей конфет, а их XOR-сумма!

XOR-сумма последовательности целых чисел a₁, a₂, ..., a_m считается как побитовый XOR всех элементов последовательности: , здесь обозначает операцию побитового XOR; подробнее про побитовый XOR (операцию, также известную как побитовое исключающее ИЛИ) можно прочитать здесь.

Дед Мороз заранее предупредил Гришу, что ему требуется посетить еще несколько мест, а потому Гриша волен выбрать не более k конфет из мешка Деда Мороза. Помогите Грише узнать, чему равна максимальная XOR-сумма, а вместе с ней и максимальное счастье, которое он может обрести при оптимальном выборе конфет.