A 按位与（and）

题目描述

小 R 有 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

小 X 给了小 R 一个正整数 $m$，并要求小 R 从这 $n$ 个非负整数中选出恰好 $m$ 个，使得选出的 $m$ 个数的二进制按位与的值最大。

你需要帮助小 R 求出，他能选出的 $m$ 个数的按位与的最大值。

输入格式

输入的第一行包含两个正整数 $n,m$。

输入的第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，依次表示小 R 的 $n$ 个非负整数。

输出格式

输出一行一个非负整数，表示小 R 能选出的 $m$ 个数的按位与的最大值。

样例

输入样例 1

4 2
3 15 12 12

输出样例 1

12

输入样例 2

5 3
31 3 1 15 7

输出样例 2

7

样例解释

样例 1：小 R 有 $4$ 个非负整数 $3,15,12,12$。

• 若选 $3,15$，按位与为 $3\ \mathrm{and}\ 15=3$；
• 若选 $3,12$，按位与为 $0$；
• 若选 $15,12$，按位与为 $12$；
• 若选 $12,12$，按位与为 $12$。

因此最大值为 $12$。

样例 2：若选 $31,15,7$，按位与为 $7$，可以证明最大值就是 $7$。

数据范围

对于所有测试数据，均有：

• $1\le m\le n\le 2\times 10^5$；
• 对于所有 $i$（$1\le i\le n$），均有 $0\le a_i<2^{30}$。

测试点编号	$n\le$	$m$	$\max a_i<$	特殊性质
$1\sim 5$	$20$	$\le n$	$2^{20}$	无
$6$	$2000$	$=1$
$7$		$=n$
$8\sim 10$		$=2$
$11,12$	$2\times 10^5$	$=n-1$
$13$		$\le n$		A
$14,15$				B
$16,17$			$4$	无
$18,19$			$2^{10}$
$20$			$2^{30}$

特殊性质 A：对于所有 $i$，存在非负整数 $k_i$ 满足 $a_i=2^{k_i}-1$。

特殊性质 B：存在非负整数 $k$ 满足 $n=2^k$，且对所有 $i$ 均有 $a_i=i-1$。

---

题目来源：CSP-J 2026 第二轮（CCF CSP-J 入门级）。 题面据洛谷 P17829 整理；本平台测试数据由官方标程生成，覆盖题面「测试点编号」表里的各档子任务。