← 返回题目列表

Codeforces · 1013/B

B. 和

中文机器翻译题面 查看原题

有一个包含 n 个元素 a1, a2, ..., an 和数字 x 的数组。

在一次运算中,您可以选择某个 i (1 ≤ i ≤ n) 并将元素 ai 替换为 ai & x,其中 & 表示按位与运算。

您希望数组在应用一些操作后至少有两个相等的元素(可能没有)。换句话说,应该至少有两个不同的索引 i ≠ j 使得 ai = aj。确定是否可以实现,如果可能,确定要应用的最少操作数。

输入

第一行包含整数 n 和 x (2 ≤ n ≤ 100 000, 1 ≤ x ≤ 100 000)、数组中元素的数量以及 to 和 with 的数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 100 000),即数组的元素。

输出

打印一个整数,表示要执行的最小操作数,如果不可能,则打印 -1。

示例

输入 #1

4 3
1 2 3 7

输出 #1

1

输入 #2

2 228
1 1

输出 #2

0

输入 #3

3 7
1 2 3

输出 #3

-1

注意

在第一个示例中,可以将操作应用于数组的最后一个元素。这样就用 3 代替了 7,所以我们一步就达到了目标。

在第二个示例中,数组已经有两个相等的元素。

在第三个示例中,应用操作根本不会更改数组,因此不可能使某些元素对相等。