Under construction

Still being built. Things may change

XNOR's Rebellion

Time limit1sMemory limit1024 MB

Summary
Given N numbers of B bits, pick a nonempty subsequence and fold it with B-bit XNOR from left to right to maximize the result.
Level

Medium6 of 10

Topics
Bit manipulation, Dynamic programming, Hash map
Solved
No attempts yet

Problem

Competitive programming problems always use only XOR, and XNOR is furious about it. It decides to start a rebellion by gathering NN non-negative integers!

XNOR is methodical, so before starting the rebellion it wants to calculate its strength first. Since this is XNOR's rebellion, the strength is the result of applying XNOR to the given numbers in order from the front. Every integer XNOR gathered can be written as an unsigned BB-bit integer, so XNOR uses XNOR on BB-bit integers.

A higher strength means a higher chance of success, so XNOR picks one or more of the NN numbers to maximize the strength. The order of the chosen numbers cannot be changed.

Input

The first line contains NN, the number of integers XNOR gathered, and BB, the number of bits XNOR uses, separated by a space. (1≤N≤200 0001\le N\le 200\,000; 1≤B≤601\le B\le 60)

The second line contains the NN non-negative integers A1,A2,…,ANA_1,A_2,\ldots,A_N in decimal form, separated by spaces. (0≤Ai<2B0\le A_{i}<2^B)

Output

Print the maximum strength of the rebellion that XNOR can produce on the first line.

Hint

The bitwise XNOR of two numbers converts both to binary and compares each bit. The result bit is 11 if the two bits match and 00 if they differ. For example, 1100(2) XNOR 0110(2)=0101(2)1100_{(2)}\text{ XNOR } 0110_{(2)}=0101_{(2)}.

Examples2

  1. Example 1

    Input
    5 3
    1 2 3 4 5
    
    Expected output
    7
    
  2. Example 2

    Input
    1 60
    1217
    
    Expected output
    1217