Problem:
 Score : 400 points    Problem Statement You are given N non-negative integers A_1, A_2, ..., A_N and another non-negative integer K .  For a integer X between 0 and K (inclusive), let f(X) = (X XOR A_1)  +  (X XOR A_2)  +  ...  +  (X XOR A_N) .  Here, for non-negative integers a and b , a XOR b denotes the bitwise exclusive OR of a and b .  Find the maximum value of f .   What is XOR?  The bitwise exclusive OR of a and b , X , is defined as follows:   When X is written in base two, the digit in the 2^k 's place ( k \geq 0 ) is 1 if, when written in base two, exactly one of A and B has 1 in the 2^k 's place, and 0 otherwise.   For example, 3 XOR 5 = 6 . (When written in base two: 011 XOR 101 = 110 .)

Solution (Python):
def main():

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    from operator import itemgetter
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd 
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    
        
        
    
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    if __name__ != '__main__':
        
        sys.stdin = open('sample.txt')
        
    
    

    N, K = R()
    A = R()
    memo = [0] * 40
    for a in A:
        bin_str_a = format(a, '
        for i, ai in enumerate(bin_str_a[2:]):
            if ai == '1':
                memo[i] += 1
    bin_str_k = format(K,'
    ans = 0
    for i,m in enumerate(reversed(memo)):
        if bin_str_k[-i-1] == '1':
            ans += max(m, N-m) * (2**i)
        else:
            ans += m * (2**i)
    dp = [0] * 42
    for i,m in enumerate(reversed(memo)):
        dp[i] = max(m, N-m) * (2**i)
    for i in range(1, 42):
        dp[i] += dp[i-1]
    
    tmp = 0
    for i,m in enumerate(memo):
        if bin_str_k[2+i] == '1' and 38-i>=0:
            ans = max(ans, tmp + m * (2**(39-i)) + dp[38-i])
            tmp += (N-m) * (2**(39-i))
            if N-m < m:
                break
        else:
            tmp += m * (2**(39-i))
            continue
    
    print(ans)
    
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

Solution (Python):
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [0] * 45
for i in c:
    e = bin(i)
    e = e[2:]
    for j in range(len(e)):
        if e[-j-1] == "1":
            d[j] += 1
f = 0
for i in range(45-1, -1, -1):
    if d[i] * 2 < a:
        f += 2 ** i
        if f > b:
            f -= 2 ** i
g = 0
for i in c:
    g += f ^ i
print(g)

Solution (Python):




import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n,k = map(int,input().split())
a = list(map(int,input().split()))

size = 40
dp = [[-1]*2 for _ in range(size+1)]
dp[0][0] = 0






for i in range(size):
    
    
    biti = 2**(size - i - 1)
    
    nbit = sum([1 for aa in a if aa & biti])
    
    score0 = biti * nbit
    
    score1 = biti * (n - nbit)
    

    
    
    if k & biti:
        dp[i+1][0] = max(dp[i+1][0],dp[i][0] + score1)
    
    else:
        dp[i+1][0] = max(dp[i+1][0],dp[i][0] + score0)

    
    
    if k & biti:
        dp[i+1][1] = max(dp[i+1][1],dp[i][0] + score0)

    
    
    
    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1],dp[i][1] + max(score0,score1))
print(max(dp[size]))

Solution (Python):
n, k = map(int, input().split())
aa = list(map(int, input().split()))
k_bit=[int(b) for b in list(format(k,"b"))]
k_bit.reverse()
m=len(k_bit)
cnt_bit = [0] * m
for a in aa:
    for i in range(m):
        cnt_bit[i] += a & 1
        a >>= 1

x_bit=[(cnt<n/2)*1 for cnt in cnt_bit]


for i in range(m-1,-1,-1):
    kb=k_bit[i]
    xb=x_bit[i]
    if kb==1 and xb==0:break
    if kb==0 and xb==1:x_bit[i]=0

x=sum(x_bit[i]*2**i for i in range(m))

print(sum(a^x for a in aa))

Solution (Python):
N,K = map(int,input().split())
*A, = map(int,input().split())

l = len(bin(K))-2
bK = bin(K)[2:]
Xide = sum(int(sum((a>>i)&1 for a in A)*2<N)<<i for i in range(l))
bXide = bin(Xide)[2:].zfill(l)

def f(x):
    return sum(x^a for a in A)

ans = f(K)
for i in range(l):
    x = int(bK[:i]+"0"+bXide[1+i:],2)
    if x>K:continue
    ans = max(ans,f(x))
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

kb = format(K, 'b')[::-1]
v = len(kb)

dp = [0]*v
for e in A:
    i = 0
    while e > 0 and i < v:
        if e % 2 == 1:
            dp[i] += 1
        e //= 2
        i += 1

bi = ""
for i in range(v):
    if dp[i] > N // 2:
        bi += "0"
    else:
        bi += "1"

bi = bi

def hoge(binary):
    res = 0
    n = int(binary[::-1], 2)
    for e in A:
        res += n ^ e
    return res


def calc(i):
    tmp = bi[:i] + "0" + bi[i+1:]
    return hoge(tmp)

ans = 0
for i in reversed(range(v)):
    if bi[i] == "1" and kb[i] == "1":
        ans = max(ans, calc(i))
    elif bi[i] == "1" and kb[i] == "0":
        bi = bi[:i] + "0" + bi[i+1:]
    elif bi[i] == "0" and kb[i] == "1":
        break

ans = max(ans, hoge(bi))

print(ans)

Solution (Python):
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [0] * 45
for i in c:
    e = bin(i)[2:]
    for j in range(len(e)):
        d[j] += 1 if e[-j-1] == "1" else 0
ans = 0
s = 0
for i in range(44, -1, -1):
    if 2 ** i + s <= b:
        if a > d[i] * 2:
            s += 2 ** i
for i in c:
    ans += i ^ s
print(ans)

Solution (Python):
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [0] * 45
for i in c:
    e = bin(i)[2:]
    for j in range(len(e)):
        d[j] += int(e[-j-1])
ans = 0
s = 0
for i in range(44, -1, -1):
    if 2 ** i + s <= b and a > d[i] * 2:
        s += 2 ** i
for i in c:
    ans += i ^ s
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

b = [0] * 40
for i in range(40):
    for k in A:
        b[i] += (k & (1 << i)) >> i

c = [0] * 40
for i in range(39):
    if b[i] > N - b[i]:
        c[i + 1] = c[i] + (b[i] << i)
    else:
        c[i + 1] = c[i] + (N - b[i] << i)

ans = 0
cnt = 0
for i in reversed(range(40)):
    if K & (1 << i):
        ans = max(ans, cnt + (b[i] << i) + c[i])
        cnt += N - b[i] << i
    else:
        cnt += b[i] << i
print(max(ans, cnt))

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
m=max(A)
m=max(m,K)
L=len(bin(m))-2
mihon=0
for k in range(L-1,-1,-1):
    s=0
    for a in A:
        s+=(a&1<<k)>>k
    mihon*=2
    mihon+=s<(N-s)


ans=0
for a in A:
    ans+=a^K
for i in range(L):
    if not(K&(1<<L-i)):
        continue
    t=(K&(((1<<L)-1)<<(L-i+1)))+(0<<L-i)+(mihon&((1<<(L-i))-1))
    s=0
    for a in A:
        s+=a^t
    ans=max(ans,s)
print(ans)

Solution (Python):
n, k = map(int, input().split())
arr = list(map(int, input().split()))

max_x = k
i = 0
xy = []
res = 0

while any(arr) > 0 or k > 0:
    sum_arr = sum(a % 2 for a in arr)
    if sum_arr < n / 2:
        xy.append([2 ** i, (n - sum_arr) * 2 ** i, sum_arr * 2 ** i])
    else:
        res += sum_arr * 2 ** i
    arr = [a // 2 for a in arr]
    k //= 2
    i += 1

for a, b, c in xy[::-1]:
    if a <= max_x:
        res += b
        max_x -= a
    else:
        res += c

print(res)

Solution (Python):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
D = 100

v0 = []
vm = []
vk = []
for i in range(D):
    n1 = 0
    for a in A:
        if a>>i &1: n1+=1
    v0.append(n1 * 2**i)
    vm.append(max(n1,N-n1) * 2**i)
    vk.append((N-n1) * 2**i if K>>i &1 else n1 * 2**i)

m = sum(vk)
for i in range(D):
    if K>>i &1: m = max(m, sum(vk[i+1:]) + v0[i] + sum(vm[:i]))

print(m)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def calcans(ans, a_list):  
  sm = 0
  for a in a_list:
    sm += a^ans
  print(sm)

def solve():
  N, K = LI()
  a_list = LI()
  if K == 0:
    calcans(0, a_list)
    return
  
  import math
  nk = math.floor(math.log2(K)) + 1
  bink = '{0:050b}'.format(K)
  bin_list = []
  for a in a_list:
    bin_list.append('{0:050b}'.format(a))

  
  bind = True
  ans = ''
  for i in range(nk, 0, -1):
    n1 = 0
    for b in bin_list:
      
      if b[-i] == '1':
        n1 += 1

    if n1 > N // 2:
      optimal = '0'
    else:
      optimal = '1'

    if bink[-i] == '1':
      ans += optimal
      if optimal == '0':
        bind = False
    else:
      if bind == True:
        ans += '0'
      else:
        ans += optimal

  ansint = int(ans, 2)
  calcans(ansint, a_list)
  
solve()

Solution (Python):
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [0] * 45
for i in c:
    e = bin(i)[2:]
    for j in range(len(e)):
        d[j] += 1 if e[-j-1] == "1" else 0
e = 0
for i in range(len(d)-1, -1, -1):
    if 2 ** i + e <= b:
        if d[i] <= len(c) // 2:
            e += 2 ** i
f = 0
for i in range(len(c)):
    f += e ^ c[i]
print(f)

Solution (Python):
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*40
for i in range(n):
  nn=A[i].bit_length()
  for j in range(nn):
    if bin(A[i])[-j-1]=="1":
      B[j]+=1

ans=sum(A)
kk=bin(k)[2:].zfill(40)
for i in range(40):
  if kk[i]=="0":
    continue
  else:
    ans1=0
    for j in range(40):
      if j<i:
        if kk[j]=="1":
          ans1+=2**(39-j)*(n-B[39-j])
        else:
          ans1+=2**(39-j)*B[39-j]
      elif j==i:
        ans1+=2**(39-j)*B[39-j]
      else:
        ans1+=2**(39-j)*max((n-B[39-j]),B[39-j])
    ans=max(ans,ans1)
ans1=0
for j in range(40):
  if kk[j]=="1":
    ans1+=2**(39-j)*(n-B[39-j])
  else:
    ans1+=2**(39-j)*B[39-j]
ans=max(ans,ans1)


print(ans)

Solution (Python):
def main():
    n, k = map(int, input().split())
    *a, = map(int, input().split())

    size = 40
    dp = [[-1 for _ in range(2)] for _ in range(size+1)]
    dp[0][0] = 0
    for i in range(size):
        biti = 2 ** (size - i - 1)
        nbit = sum([1 for aa in a if aa & biti])
        score0 = biti * nbit
        score1 = biti * (n - nbit)

        
        if k & biti:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + score1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + score0)

        
        if k & biti:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + score0)

        
        if dp[i][1] != -1:
            dp[i+1][1] = max(dp[i+1][1], dp[i][1] + max(score0, score1))
    print(max(dp[size]))


main()

Solution (Python):
n, k = map(int, input().split())
a = tuple(map(int, input().split()))

MAX_DIGIT = 50

bits = [0] * (MAX_DIGIT + 1)






for j in range(MAX_DIGIT + 1):
    bits[j] = sum(1 for aa in a if (aa >> j) & 1)

dp = [[0] * 2 for _ in range(MAX_DIGIT + 1)]




for j in reversed(range(MAX_DIGIT)):
    
    if (k >> j) & 1:
        
        dp[j][0] = dp[j + 1][0] + (n - bits[j]) * (1 << j)
        if dp[j + 1][1] == 0:
            dp[j][1] = dp[j + 1][0] + bits[j] * (1 << j)
        else:
            dp[j][1] = max(
                dp[j + 1][0] + bits[j] * (1 << j),
                dp[j + 1][1] + max(bits[j], n - bits[j]) * (1 << j)
            )

    else:
        
        dp[j][0] = dp[j + 1][0] + bits[j] * (1 << j)
        if dp[j + 1][1] == 0:
            dp[j][1] = 0
        else:
            dp[j][1] = dp[j + 1][1] + max(bits[j], n - bits[j]) * (1 << j)

print(max(
    dp[0][0],
    dp[0][1]
))

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
x = list(map(int, input().split()))
a = 0
b = 0
ans = 0
mae = 0
b = [0] * 40
for i in range(40):
    for k in x:
        b[i] += (k & (1 << i)) >> i
c = [0] * 40
for i in range(39):
    if b[i] > n - b[i]:
        c[i+1] = c[i] + (b[i] << i)
    else:
        c[i+1] = c[i] + (n - b[i] << i)
for i in range(39, -1, -1):
    if m & (1 << i):
        ansb = mae
        ansb += b[i] << i
        ansb += c[i]
        if ans < ansb:
            ans = ansb
        mae += n-b[i] << i
    else:
        mae += b[i] << i
ans = max(ans, mae)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
x = list(map(int, input().split()))
a = 0
b = 0
ans = 0
mae = 0
b = [0] * 40
for i in range(40):
    for k in x:
        b[i] += (k & (1 << i)) >> i
c = [0] * 40
for i in range(1,40):
    if b[i-1] > n - b[i-1]:
        c[i] = c[i - 1] + (b[i - 1] << i - 1)
    else:
        c[i] = c[i - 1] + (n - b[i - 1] << i - 1)
for i in range(39, -1, -1):
    if m & (1 << i):
        ansb = mae
        ansb += b[i] << i
        ansb += c[i]
        if ans < ansb:
            ans = ansb
        mae += n-b[i] << i
    else:
        mae += b[i] << i
ans = max(ans, mae)
print(ans)

Solution (Python):



"""
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = sum(l) - 2*l[-1]
if ans > 0:
    print("Yes")
else:
    print("No")
"""


"""
import bisect
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
xb = [abs(x[i] - x[i + 1]) for i in range(m-1)]
xb.sort(reverse=True)
ans = sum(xb[n - 1::])
print(ans)
"""


import sys
input = sys.stdin.readline
n, m = map(int, input().split())
x = list(map(int, input().split()))
a = 0
b = 0
ans = 0
ansb = 0
mae = 0
b = [0] * 40
for i in range(40):
    for k in x:
        b[i] += (k & (1 << i)) >> i

for i in range(39, -1, -1):
    if m & (1 << i):
        ansb = mae
        ansb += b[i] << i
        for k in range(i):
            if b[k] > n - b[k]:
                ansb += b[k] << k
            else:
                ansb += n - b[k] << k
        if ans < ansb:
            ans = ansb
        mae += n-b[i] << i
    else:
        mae += b[i] << i
ans = max(ans, mae)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
k, tmp = 0, K
while tmp > 0:
    tmp //= 2
    k += 1
tight = 0
untight = 0
for j in range(k)[::-1]:
    cnt0, cnt1 = 0, 0
    for a in A:
        if (a >> j) & 1:
            cnt1 += 1
        else:
            cnt0 += 1
    b = 2**j
    tmp = b * max(cnt0, cnt1)
    if (K >> j) & 1:
        if j == k-1:
            untight = b * cnt1
        else:
            untight = max(tight + b * cnt1, untight + tmp)
        tight += tmp
    else:
        tight += b * cnt1
        untight += tmp
ans = max(tight, untight)
for a in A:
    ans += (a >> k) << k
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
k, tmp = 0, K
while tmp > 0:
    tmp //= 2
    k += 1
tight = 0
untight = 0
for j in range(k)[::-1]:
    
    cnt0, cnt1 = 0, 0
    for a in A:
        
        if (a >> j) & 1:
            cnt1 += 1
        else:
            cnt0 += 1
    b = 2**j
    tmp = b * max(cnt0, cnt1)
    if (K >> j) & 1:
        if j == k-1:
            untight = b * cnt1
        else:
            untight = max(tight + b * cnt1, untight + tmp)
        tight += tmp
    else:
        tight += b * cnt1
        untight += tmp
    
    
    
    
ans = max(tight, untight)
for a in A:
    ans += (a >> k) << k
print(ans)

Solution (Python):
n,k = [int(x) for x in input().split()]
a = [list(map(int, list(bin(int(x))[2:]))) for x in input().split()]
b = list(map(int, list(bin(k)[2:])))
m = len(b)
for i in a:
    m = max(m,len(i))
for j in range(m-len(b)):
    b.insert(0,0)
s = [n]*m
for i in a:
    k = m-len(i)
    for j in range(len(i)):
        if i[j]:
            s[k+j] -= 1
dp = [[0 for i in range(2)] for k in range(m)]
dp[-1][1] = -float("inf")
f = [1<<(m-i-1) for i in range(m)]
for i in range(m):
    for j in range(2):
        x = 1 if j else b[i]
        for d in range(x+1):
            j_ = j | (d < b[i])
            k = dp[i-1][j]+f[i]*(s[i]*d+(n-s[i])*(1-d))
            if k > dp[i][j_]:
                dp[i][j_] = k
print(max(dp[m-1]))

Solution (Python):
n,k = [int(x) for x in input().split()]
a = [list(map(int, list(bin(int(x))[2:]))) for x in input().split()]
b = list(map(int, list(bin(k)[2:])))
m = len(b)
for i in a:
    m = max(m,len(i))
for j in range(m-len(b)):
    b.insert(0,0)
s = [n]*m
for i in a:
    k = m-len(i)
    for j in range(len(i)):
        if i[j]:
            s[k+j] -= 1

dp = [[0 for i in range(2)] for k in range(m+1)]
dp[0][1] = -float("inf")
f = [1<<(m-i-1) for i in range(m)]
for i in range(m):
    for j in range(2):
        x = 1 if j else b[i]
        for d in range(x+1):
            j_ = j | (d < b[i])
            k = dp[i][j]+f[i]*(s[i]*d+(n-s[i])*(1-d))
            if k > dp[i+1][j_]:
                dp[i+1][j_] = k
print(max(dp[m]))

Solution (Python):
n,k = [int(x) for x in input().split()]
a = [list(map(int, list(bin(int(x))[2:]))) for x in input().split()]
b = list(map(int, list(bin(k)[2:])))
m = len(b)
for i in a:
    m = max(m,len(i))
for i in range(n):
    for j in range(m-len(a[i])):
        a[i].insert(0,0)
for j in range(m-len(b)):
    b.insert(0,0)
s = [0]*m
for i in a:
    for j in range(m):
        if not i[j]:
            s[j] += 1
dp = [[0 for i in range(2)] for k in range(m+1)]
dp[0][1] = -float("inf")
f = [1<<(m-i-1) for i in range(m)]
for i in range(m):
    for j in range(2):
        x = 1 if j else b[i]
        for d in range(x+1):
            j_ = j | (d < b[i])
            k = dp[i][j]+f[i]*(s[i]*d+(n-s[i])*(1-d))
            if k > dp[i+1][j_]:
                dp[i+1][j_] = k
print(max(dp[m]))

Solution (Python):
n,k = [int(x) for x in input().split()]
a = [list(map(int, list(bin(int(x))[2:]))) for x in input().split()]
b = list(map(int, list(bin(k)[2:])))
m = len(b)
for i in a:
    m = max(m,len(i))
for i in range(n):
    for j in range(m-len(a[i])):
        a[i].insert(0,0)
for j in range(m-len(b)):
    b.insert(0,0)
s = [[0,0] for i in range(m)]
for i in a:
    for j in range(m):
        s[j][1-i[j]] += 1
dp = [[0 for i in range(2)] for k in range(m+1)]
dp[0][1] = -float("inf")
f = [1<<(m-i-1) for i in range(m)]
for i in range(m):
    for j in range(2):
        x = 1 if j else b[i]
        for d in range(x+1):
            j_ = j | (d < b[i])
            k = dp[i][j]+f[i]*s[i][d]
            if k > dp[i+1][j_]:
                dp[i+1][j_] = k
print(max(dp[m]))

Solution (Python):
n,k = [int(x) for x in input().split()]
a = [list(map(int, list(bin(int(x))[2:]))) for x in input().split()]
b = list(map(int, list(bin(k)[2:])))
m = len(b)
for i in a:
    m = max(m,len(i))
for i in range(n):
    for j in range(m-len(a[i])):
        a[i].insert(0,0)
for j in range(m-len(b)):
    b.insert(0,0)
s = [[0,0] for i in range(m)]
for i in a:
    for j in range(m):
        s[j][1-i[j]] += 1
dp = [[0 for i in range(2)] for k in range(m+1)]
dp[0][1] = -float("inf")
f = [1<<(m-i-1) for i in range(m)]
for i in range(m):
    for j in range(2):
        x = 1 if j else b[i]
        for d in range(x+1):
            dp[i+1][j | (d < b[i])] = max(dp[i+1][j | (d < b[i])], dp[i][j]+f[i]*s[i][d])

print(max(dp[m]))

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
a=len(format(max(l),"b"))
x=[None]*n
xl=[0]*a
for i in range(n):
  b=format(l[i],"b")
  x[i]=b.zfill(a)
for i in range(a):
  for j in range(n):
    if x[j][i]=="1":
      xl[i]+=1
c=format(k,"b")
if len(c)>a:
  c,d=c[:len(c)-a],c[len(c)-a:]
  ans=int("0b"+c,2)*(2**a)*n
  check=0
  for i in range(a):
    if check==0:
      if d[i]=="1":
        if xl[i]>=n-xl[i]:
          ans+=xl[i]*(2**(a-i-1))
          check=1
        else:ans+=(n-xl[i])*(2**(a-i-1))
      else:ans+=xl[i]*(2**(a-i-1))
    else:
      ans+=max(xl[i],n-xl[i])*(2**(a-i-1))
else:
  c=c.zfill(a)
  ans=0
  check=0
  for i in range(a):
    if check==0:
      if c[i]=="1":
        if xl[i]>=n-xl[i]:
          ans+=xl[i]*(2**(a-i-1))
          check=1
        else:ans+=(n-xl[i])*(2**(a-i-1))
      else:ans+=xl[i]*(2**(a-i-1))
    else:
      ans+=max(xl[i],n-xl[i])*(2**(a-i-1))
print(ans)

Solution (Python):
n,k = map(int,input().split())

a = list(map(int,input().split()))

x = 0
for i in range(40,-1,-1):
    if x | (1 << i) > k:
        continue
    cnt = 0
    for j in range(n):
        if a[j] & (1 << i) == 0:
            cnt += 1
    
    if cnt > n - cnt:
        x = x | (1 << i)

ans = 0
for i in range(n):
    ans += x ^ a[i]

print(ans)

Solution (Python):
import math
import sys
input = sys.stdin.readline

def main():
    num, k = map(int, input().split())
    data = list(map(int, input().split()))

    count_list = [0 for i in range(40)]

    for i in range(num):
        now_bin = bin(data[i])[2:]
        now_bin = now_bin.zfill(40)
        for j in range(40):
            if now_bin[j] == '1':
                count_list[j] += 1

    ans_bin = ''
    max_bin = bin(k)[2:]
    max_bin = max_bin.zfill(40)
    large_flg = 0



    for i in range(40):
        if count_list[i] >= math.ceil(num / 2):
            if max_bin[i] == '1':
                large_flg = 1
            ans_bin += '0'
        else:
            if max_bin[i] == '1' or large_flg:
                ans_bin += '1'
            else:
                ans_bin += '0'

    ans_int = int(ans_bin, 2)
    
    ans = 0
    for i in range(num):
        ans += ans_int ^ data[i]

    print(ans)





if __name__ == '__main__':
    main()

Solution (Python):
N , K = map(int,input().split())
 
A = list(map(int,input().split()))
 
A.sort()
 
maxDigit = max(K,A[-1]).bit_length()
 

maxVal = [0] * maxDigit
for i in range(maxDigit) :
    count = 0
    mask = 2**i
    for a in A :
        count += (a & mask) // mask
    count = max(N - count, count)
    if i == 0 :
        maxVal[0] = count
    else :
        maxVal[i] = count * mask + maxVal[i-1]
 
valK = [0] * (maxDigit + 1)
for i in range(maxDigit-1, -1, -1) :
    mask = 2**i
    maskK = K & mask
    sumK = 0
    for a in A :
        val = a & mask
        if maskK != val :
            sumK += mask
    valK[i] = sumK + valK[i+1]
 
ans = valK[0]  
for i in range(maxDigit-1, -1, -1) :  
    if not K & (2**i) > 0  :  
        continue
 
    sumXor = valK[i+1]
 
    
    mask = 2**i
    for n in range(N) :
        if A[n] & mask > 0 :
            sumXor += mask
 
    if i > 0 :
        sumXor += maxVal[i-1]
 
    ans = max(ans, sumXor)
 
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
BIT_NUM = K.bit_length()

X = 0
flag = False
for i in reversed(range(BIT_NUM)):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    if flag:
        if N - cnt > cnt:
            X |= 1 << i
        continue
    kbit = (K >> i) & 1
    if N - cnt > cnt and kbit:
        
        X |= 1 << i
    else:
        if kbit:
            
            flag = True

print(sum([X ^ a for a in A]))

Solution (Python):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
A = np.array(A)

S = A.sum()
ddp = np.full(((10 ** 12).bit_length() + 1, 2), -IINF, dtype=np.int64)
ddp[-1][0] = 0
for d in reversed(range(len(ddp) - 1)):
    mask = 1 << d
    xxor = ((A ^ mask) & mask).sum()
    nxor = (A & mask).sum()

    if K & mask > 0:
        ddp[d, 0] = max(ddp[d, 0], ddp[d + 1, 0] + xxor)
        ddp[d, 1] = max(ddp[d, 1], ddp[d + 1, 0] + nxor)
    else:
        ddp[d, 0] = max(ddp[d, 0], ddp[d + 1, 0] + nxor)
    ddp[d, 1] = max(ddp[d, 1], ddp[d + 1, 1] + xxor)
    ddp[d, 1] = max(ddp[d, 1], ddp[d + 1, 1] + nxor)
print(int(ddp[0, :].max()))

Solution (Python):
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
ans = 0
tmp = 0

for i in range(40, -1, -1):
    onenum = 0
    for j in A:
        if 2**i & j == 2**i:
            onenum += 1
    
    zeronum = N - onenum
    
    if tmp + 2**i > K:
        ans += onenum * 2**i
    else:
        if onenum > zeronum:
            ans += onenum * 2**i
        else:
            ans += zeronum * 2**i
            tmp += 2**i

print(ans)