Іспит

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 256 мегабайтів

Після вживання великого об'єму компотику люди втрачають змогу правильно рахувати. Саме така історія трапилася з нашим героєм. Він був впевнений, що йому вистачає набраних за семестр балів, щоб мати змогу скласти іспит. На жаль, він помилився в розрахунках. Йому не вистачає однієї задачі, а екзамен вже завтра, допоможіть йому та розв'яжіть цю задачу.

Вам дано масив $a$ , який складається з $n$ цілих чисел та ціле число $k$ . Ми називаємо масив $b$ з $t$ елементів гарним, якщо виконується popcount $(b_{1} ∣ b_{2} ∣ \dots b_{t - 1} ∣ b_{t}) \geq k$ , де $∣$ позначає операцію побітового АБО, а popcount( $x$ ) — функція, яка повертає кількість одиниць у бітовому записі числа $x$ . Дисбаланс масиву $b$ дорівнює max(b) - min(b), де max і min позначають максимальний та мінімальний елементи масиву $b$ відповідно.

Знайдіть найменше значення дисбалансу серед усіх гарних підпослідовностей масиву $a$ . Якщо такої підпослідовності не існує, виведіть "-1".

Побітове АБО між двома числами $a$ і $b$ визначається для кожного біта окремо. Якщо в числі $a$ $i$ -й біт дорівнює $1$ , або в числі $b$ він дорівнює $1$ , то і в значенні побітового АБО він буде дорівнювати $1$ . Наприклад, $5_{10} ∣ 9_{10}$ = $010 1_{2} ∣100 1_{2}$ = $110 1_{2}$ = $1 3_{10}$ .

Масив $c$ є підпослідовністю масиву $a$ , якщо масив $c$ можна отримати з масиву $a$ шляхом видалення декількох (можливо, нуля) елементів.

Вхідні дані

Перший рядок містить два цілі числа $n$ ( $1 \leq n \leq 1 0^{6}$ ) і $k$ ( $1 \leq k \leq 30$ ).

Другий рядок містить $n$ цілих чисел $a_{i}$ ( $0 \leq a_{i} < 2^{30}$ ).

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Вхідні дані #3

Відповідь #3

Примітка

Пояснення до першого прикладу:

Можна обрати $b$ = ${3}$ , або $b$ = ${5}$ , оскільки $3$ = $1 1_{2}$ та $5$ = $10 1_{2}$ і popcount $(3)$ = popcount $(5)$ = $2$ , що дорівнює $k$ = $2$ .

Пояснення до другого прикладу:

Можна обрати $b$ = ${7, 8}$ , popcount $(7∣8)$ = popcount $(011 1_{2} ∣100 0_{2})$ = popcount $(111 1_{2})$ = $4$ , що дорівнює $k$ = $4$ .

Пояснення до третього прикладу:

Можна показати, що не існує такої підпослідовності $b$ масиву $a$ , що задовольняє умовам.

Оцінювання

Гарантується, що рішення, які працюють правильно при $n \leq 20$ набиратимуть принаймні $5$ балів.

Гарантується, що рішення, які працюють правильно при $a_{i} < 1024$ набиратимуть принаймні $15$ балів.

Гарантується, що рішення, які працюють правильно при $n \leq 1 0^{5}$ набиратимуть принаймні $85$ балів.