수 색칠하기

음이 아닌 정수 배열 $a_1, a_2, \ldots, a_n$과 정수 $k$가 주어진다. 두 인덱스 $i, j$가 다음 두 조건을 모두 만족하면 충돌한다고 한다.

1. $a_i \operatorname{AND} a_j = a_i$
2. $a_i \operatorname{XOR} a_j$를 이진수로 나타냈을 때 1인 비트가 $k$개 이상이다.

여기서 AND는 비트별 AND 연산이고, XOR은 비트별 배타적 논리합 연산이다.

$m$개의 색으로 이루어진 일관된 색칠은 $1 \le c_i \le m$을 만족하는 정수 배열 $c_1, \ldots, c_n$이며, 충돌하는 어떤 인덱스 쌍 $i, j$에 대해서도 $c_i = c_j$가 아닌 배열이다.

$a_1, \ldots, a_n$의 일관된 색칠에 필요한 색의 최소 개수를 구하라.

첫 줄에 두 정수 $n, k$ ($1 \leq n, k \leq 5 \cdot 10^5$)가 주어진다.

다음 줄에 $n$개의 정수 $a_i$ ($0 \leq a_i < 2^{22}$)가 주어진다.

일관된 색칠에 필요한 색의 최소 개수를 한 줄에 출력한다.

두 가지 색으로 된 일관된 색칠의 한 예는 $1, 1, 1, 2$이다. 인덱스 2와 4가 충돌하므로 색이 하나로는 부족하다.