#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1234567890;
const long long int MOD = 100000000 + 7;
const double PI = acos(-1.0);
const double EPS = 1e-10;
template <class T>
inline T CHM(T a, T M) {
  return a >= M ? a % M : a;
}
template <class T>
inline T POW(T b, T e) {
  T multiply = 1;
  for (T i = 0; i < e; i++) multiply *= b;
  return multiply;
}
template <class T>
inline T POWMOD(T b, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * b) % M;
    b = (b * b) % M;
  }
  return (T)ret;
}
template <class T>
inline T MMI(T a, T M) {
  return POWMOD(a, M - 2, M);
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
inline void speed() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
void solve() {
  int n, k, x, p;
  cin >> n >> k >> p;
  vector<long long int> arr, prefix(n), suffix(n);
  for (int(i) = (0); (i) < (n); (i)++) {
    cin >> x;
    arr.emplace_back(x);
    prefix[i] = x | prefix[max(i - 1, 0)];
  }
  for (int(i) = (n - 1); i >= (0); (i)--) {
    suffix[i] = arr[i] | suffix[min(i + 1, n - 1)];
  }
  long long int ans = 0;
  if (n == 1) {
    cout << arr[0] * POW(p, k);
    return;
  }
  for (int(i) = (0); (i) < (n); (i)++) {
    if (i == 0)
      ans = max(ans, ((long long int)arr[i] * POW(p, k)) | suffix[i + 1]);
    else if (i == n - 1)
      ans = max(ans, prefix[i - 1] | ((long long int)arr[i] * POW(p, k)));
    else
      ans = max(ans, prefix[i - 1] | ((long long int)arr[i] * POW(p, k)) |
                         suffix[i + 1]);
  }
  cout << ans;
}
int main() {
  speed();
  solve();
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

You are given n numbers a1, a2, ..., an. You can perform at most k operations. For each operation you can multiply one of the numbers by x. We want to make <image> as large as possible, where <image> denotes the bitwise OR. 

Find the maximum possible value of <image> after performing at most k operations optimally.

Input

The first line contains three integers n, k and x (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8).

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).

Output

Output the maximum value of a bitwise OR of sequence elements after performing operations.

Examples

Input

3 1 2
1 1 1


Output

3


Input

4 2 3
1 2 4 8


Output

79

Note

For the first sample, any possible choice of doing one operation will result the same three numbers 1, 1, 2 so the result is <image>. 

For the second sample if we multiply 8 by 3 two times we'll get 72. In this case the numbers will become 1, 2, 4, 72 so the OR value will be 79 and is the largest possible result.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1234567890;
const long long int MOD = 100000000 + 7;
const double PI = acos(-1.0);
const double EPS = 1e-10;
template <class T>
inline T CHM(T a, T M) {
  return a >= M ? a % M : a;
}
template <class T>
inline T POW(T b, T e) {
  T multiply = 1;
  for (T i = 0; i < e; i++) multiply *= b;
  return multiply;
}
template <class T>
inline T POWMOD(T b, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * b) % M;
    b = (b * b) % M;
  }
  return (T)ret;
}
template <class T>
inline T MMI(T a, T M) {
  return POWMOD(a, M - 2, M);
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
inline void speed() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
void solve() {
  int n, k, x, p;
  cin >> n >> k >> p;
  vector<long long int> arr, prefix(n), suffix(n);
  for (int(i) = (0); (i) < (n); (i)++) {
    cin >> x;
    arr.emplace_back(x);
    prefix[i] = x | prefix[max(i - 1, 0)];
  }
  for (int(i) = (n - 1); i >= (0); (i)--) {
    suffix[i] = arr[i] | suffix[min(i + 1, n - 1)];
  }
  long long int ans = 0;
  if (n == 1) {
    cout << arr[0] * POW(p, k);
    return;
  }
  for (int(i) = (0); (i) < (n); (i)++) {
    if (i == 0)
      ans = max(ans, ((long long int)arr[i] * POW(p, k)) | suffix[i + 1]);
    else if (i == n - 1)
      ans = max(ans, prefix[i - 1] | ((long long int)arr[i] * POW(p, k)));
    else
      ans = max(ans, prefix[i - 1] | ((long long int)arr[i] * POW(p, k)) |
                         suffix[i + 1]);
  }
  cout << ans;
}
int main() {
  speed();
  solve();
  return 0;
}

```