시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB222100.000%

문제

You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$ and an integer $k$. Two indices $i, j$ are called inconsistent if both of the two conditions hold:

  1. $a_i \text{ }\mathrm{AND}\text{ } a_j = a_i$,
  2. Binary representation of $(a_i \text{ }\mathrm{XOR}\text{ } a_j)$ have at least $k$ bits set to $1$.

Here $\mathrm{AND}$ stands for bitwise and operation, $\mathrm{XOR}$ stands for bitwise exclusive-OR operation.

A consistent coloring of $a_1, \ldots, a_n$ in $m$ colors is an array of $n$ integers $c_1, \ldots, c_n$ ($1 \leq c_i \leq m$) such that there is no pair of inconsistent indices $i, j$ with $c_i = c_j$.

Your task is to find the smallest possible number of colors in a consistent coloring of $a_1, \ldots, a_n$.

입력

In the first line you are given two integers $n, k$ ($1\leq n, k\leq 5\cdot 10^5$).

In the next line you are given $n$ integers $a_i$ ($0\leq a_i < 2^{22}$).

출력

Print one integer --- the smallest number of colors in a consistent coloring.

예제 입력 1

4 1
1 2 4 6

예제 출력 1

2

노트

One possible consistent coloring in two colors is $1, 1, 1, 2$. Since indices $2$ and $4$ are inconsistent, one color is not enough.