C. 按位与 / and
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

Input

从标准输入读入数据。

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

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

Output

输出到标准输出。

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

Examples
Input
4 2
3 15 12 12
Output
12
Input
5 3
31 3 1 15 7
Output
7
Note

补充样例文件可从原题页面的附件下载：https://www.luogu.com.cn/problem/P17829。

样例 1 解释

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

  • 若小 R 选择 $$$3,15$$$，则按位与的值为 $$$3\mathbin{\mathrm{and}}15=3$$$；
  • 若小 R 选择 $$$3,12$$$，则按位与的值为 $$$3\mathbin{\mathrm{and}}12=0$$$；
  • 若小 R 选择 $$$15,12$$$，则按位与的值为 $$$15\mathbin{\mathrm{and}}12=12$$$；
  • 若小 R 选择 $$$12,12$$$，则按位与的值为 $$$12\mathbin{\mathrm{and}}12=12$$$。

因此，小 R 能选出的 $$$m$$$ 个数的按位与的最大值为 $$$12$$$。

样例 2 解释

若小 R 选择 $$$31,15,7$$$，则按位与的值为 $$$31\mathbin{\mathrm{and}}15\mathbin{\mathrm{and}}7=7$$$。可以证明，小 R 能选出的 $$$m$$$ 个数的按位与的最大值为 $$$7$$$。

样例 3

见题目目录下的 and/3.in 与 and/3.ans。

该样例满足测试点 $$$8\sim 10$$$ 的约束条件。

样例 4

见题目目录下的 and/4.in 与 and/4.ans。

该样例满足测试点 $$$14,15$$$ 的约束条件。

样例 5

见题目目录下的 and/5.in 与 and/5.ans。

该样例满足测试点 $$$18,19$$$ 的约束条件。

数据范围

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

  • $$$1\le m\le n\le 2\times 10^5$$$；
  • 对于所有 $$$i$$$（$$$1\le i\le n$$$），均有 $$$0\le a_i \lt 2^{30}$$$。
测试点编号$$$n\le$$$$$$m$$$$$$\max_{i=1}^{n}a_i\lt$$$特殊性质
$$$1\sim 5$$$$$$20$$$$$$\le n$$$$$$2^{20}$$$无
$$$6$$$$$$2000$$$$$$=1$$$$$$2^{20}$$$无
$$$7$$$$$$2000$$$$$$=n$$$$$$2^{20}$$$无
$$$8\sim 10$$$$$$2000$$$$$$=2$$$$$$2^{20}$$$无
$$$11,12$$$$$$2\times 10^5$$$$$$=n-1$$$$$$2^{20}$$$无
$$$13$$$$$$2\times 10^5$$$$$$\le n$$$$$$2^{20}$$$A
$$$14,15$$$$$$2\times 10^5$$$$$$\le n$$$$$$2^{20}$$$B
$$$16,17$$$$$$2\times 10^5$$$$$$\le n$$$$$$4$$$无
$$$18,19$$$$$$2\times 10^5$$$$$$\le n$$$$$$2^{10}$$$无
$$$20$$$$$$2\times 10^5$$$$$$\le n$$$$$$2^{30}$$$无

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

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

本题满分 100 分。官方测试点共 20 个，每个测试点 5 分，独立计分。展示样例中，与官方测试点完全相同的样例保留原测试点分值；其余样例不计分。