Everlasting love

0

0 votes
Medium
Problem

Bimlu loves arrays while his roommate Suyu loves numeric operations on a number. Underestimating their true love towards each other, Guppi wants to check if they actually love each other to that extent by asking them a problem.

Given N integers a1,a2,... an, Bimlu and Suyu have to perform at most k operations. For each operation, they can multiply one of the N numbers by x. Guppi asks them to maximize a1|a2|a3|... an, where | means Bitwise OR.

You need to help Bimlu and Suyu achieve the maximum possible value of a1|a2|a3|... an after performing at most k operations optimally.

INPUT:

The first line contains three integers, N, x, and k. The second line contains N space separated positive integers.

OUTPUT:

Output the maximum value of bitwise OR operation of the N elements after performing the operations.

CONSTRAINTS:

1 ≤ N ≤ 200000

2 ≤ x ≤ 8

1 ≤ k ≤ 10

1 ≤ ai ≤109

EXAMPLES :

1:

Input:

3 2 1

1 1 1

Output:

3

2:

Input:

4 3 2

1 2 4 8

Output:

79

EXPLANATION:

For the first sample, any possible choice of doing one operation will result the same three numbers 1, 1, 2, so the result is 1|1|2 = 3.

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.

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?