给你 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,并且是最大可能结果。