给定一个包含 $n$ 个非负整数的数组 $a_1, a_2, \dots, a_n$ 和一个整数 $k$。如果两个下标 $i, j$ 同时满足以下两个条件，则称它们是“不相容的”：

1. $a_i \text{ AND } a_j = a_i$
2. $(a_i \text{ XOR } a_j)$ 的二进制表示中至少有 $k$ 个位为 1。

其中 AND 表示按位与运算，XOR 表示按位异或运算。

$a_1, \dots, a_n$ 的 $m$ 色相容染色是指一个包含 $n$ 个整数的数组 $c_1, \dots, c_n$ ($1 \le c_i \le m$)，使得不存在任何一对不相容的下标 $i, j$ 满足 $c_i = c_j$。

你的任务是找到 $a_1, \dots, a_n$ 相容染色所需的最少颜色数量。

输入格式

第一行包含两个整数 $n, k$ ($1 \le n, k \le 5 \cdot 10^5$)。

第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i < 2^{22}$)。

输出格式

输出一个整数，表示相容染色所需的最少颜色数量。

样例

样例输入 1

4 1
1 2 4 6

样例输出 1

2

说明

一种可能的双色相容染色方案是 $1, 1, 1, 2$。由于下标 $2$ 和 $4$ 是不相容的，因此一种颜色是不够的。