← 返回题目列表

Codeforces · 578/B

B. “或”游戏

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

给你 n 个数字 a1, a2, ..., an。您最多可以执行 k 个操作。对于每个运算,您可以将其中一个数字乘以 x。我们想让 $${ a _ { 1 } } \mid { a _ { 2 } } \mid \ldots \mid { a _ { n } }$$ 尽可能大,其中 $$\text{文本不呈现为方程式,而是呈现为纯文本。}$$ 表示按位或。

在最佳执行最多 k 个操作后,找到 $${ a _ { 1 } } \mid { a _ { 2 } } \mid \ldots \mid { a _ { n } }$$ 的最大可能值。

输入

第一行包含三个整数 n、k 和 x (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8)。

第二行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 109)。

输出

执行运算后输出序列元素按位或的最大值。

示例

输入 #1

3 1 2
1 1 1

输出 #1

3

输入 #2

4 2 3
1 2 4 8

输出 #2

79

注意

对于第一个示例,执行一个操作的任何可能选择都将产生相同的三个数字 1、1、2,因此结果为 $$1 \mid 1 \mid 2 = 3$$。

对于第二个样本,如果我们将 8 乘以 3 两次,我们将得到 72。在这种情况下,数字将变为 1、2、4、72,因此 OR 值将为 79,并且是最大可能结果。