题目描述

给定一个长度为$N$的非负整数序列：$A=(A_1,A_2,\\dots,A_N)$。你最多可以进行以下操作$M$次（可以是零次）：

• 选择一个整数$i$，使得$1 \\le i \\le N$，并将$A_i$加$1$。

然后，你需要选择$K$个$A$中的元素。

找出你所选择元素的按位 $\\mathrm{AND}$ 运算的最大可能值。

什么是按位 ${\\rm AND}$ 运算？

非负整数 $A$ 和 $B$ 的按位 ${\\rm AND}$ 运算，记作 $A\\ \\mathrm{AND}\\ B$，定义如下：

• 当以二进制表示时，$A\\ \\mathrm{AND}\\ B$ 的第 $2^k$ 位（$k \\geq 0$）的数字为 $1$，当且仅当 $A$ 和 $B$ 在该位都是 $1$，否则为 $0$。

例如，$3\\ \\mathrm{AND}\\ 5 = 1$。 （在二进制表示中，$011\\ \\mathrm{AND}\\ 101 = 001$。）
通常情况下，$k$ 个非负整数 $p_1, p_2, p_3, \\dots, p_k$ 的按位 ${\\rm AND}$ 运算定义为 $(\\dots ((p_1\\ \\mathrm{AND}\\ p_2)\\ \\mathrm{AND}\\ p_3)\\ \\mathrm{AND}\\ \\dots\\ \\mathrm{AND}\\ p_k)$。我们可以证明，这个值不依赖于 $p_1, p_2, p_3, \\dots, p_k$ 的顺序。

​

约束条件

• $1 \\le K \\le N \\le 2 \\times 10^5$
• $0 \\le M < 2^{30}$
• $0 \\le A_i < 2^{30}$
• 输入中的所有值都为整数。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $M$ $K$ $A_1$ $A_2$ $\\dots$ $A_N$

输出

打印答案。

示例输入1

4 8 2
1 2 4 8

示例输出1

10

如果按照以下操作，你所选择元素的按位 $\\mathrm{AND}$ 运算的结果将是 $10$。

• 将操作应用于 $A_3$ 六次。现在，$A_3 = 10$。
• 将操作应用于 $A_4$ 两次。现在，$A_4 = 10$。
• 选择 $A_3$ 和 $A_4$，它们的按位 $\\mathrm{AND}$ 结果为 $10$。

没有办法选择两个按位 $\\mathrm{AND}$ 结果大于 $10$ 的元素，所以答案是 $10$。

示例输入2

5 345 3
111 192 421 390 229

示例输出2

461