At a break Vanya came to the class and saw an array of $n$ $k$-bit integers $a_1, a_2, \ldots, a_n$ on the board. An integer $x$ is called a $k$-bit integer if $0 \leq x \leq 2^k - 1$. 

Of course, Vanya was not able to resist and started changing the numbers written on the board. To ensure that no one will note anything, Vanya allowed himself to make only one type of changes: choose an index of the array $i$ ($1 \leq i \leq n$) and replace the number $a_i$ with the number $\overline{a_i}$. We define $\overline{x}$ for a $k$-bit integer $x$ as the $k$-bit integer such that all its $k$ bits differ from the corresponding bits of $x$. 

Vanya does not like the number $0$. Therefore, he likes such segments $[l, r]$ ($1 \leq l \leq r \leq n$) such that $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r \neq 0$, where $\oplus$ denotes the bitwise XOR operation. Determine the maximum number of segments he likes Vanya can get applying zero or more operations described above.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \leq n \leq 200\,000$, $1 \leq k \leq 30$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 2^k - 1$), separated by spaces — the array of $k$-bit integers.


-----Output-----

Print one integer — the maximum possible number of segments with XOR not equal to $0$ that can be obtained by making several (possibly $0$) operations described in the statement.


-----Examples-----
Input
3 2
1 3 0

Output
5
Input
6 3
1 4 4 7 3 4

Output
19


-----Note-----

In the first example if Vasya does not perform any operations, he gets an array that has $5$ segments that Vanya likes. If he performs the operation with $i = 2$, he gets an array $[1, 0, 0]$, because $\overline{3} = 0$ when $k = 2$. This array has $3$ segments that Vanya likes. Also, to get an array with $5$ segments that Vanya likes, he can perform two operations with $i = 3$ and with $i = 2$. He then gets an array $[1, 0, 3]$. It can be proven that he can't obtain $6$ or more segments that he likes.

In the second example, to get $19$ segments that Vanya likes, he can perform $4$ operations with $i = 3$, $i = 4$, $i = 5$, $i = 6$ and get an array $[1, 4, 3, 0, 4, 3]$.

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict
n, k = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
h = defaultdict(int)
for i in range(n):
	a[i + 1] ^= a[i]
for i in range(n + 1):
	h[min(a[i] ^ ((1 << k) - 1), a[i])] += 1
ans = 0
for x, t in list(h.items()):
	a = t // 2
	b = t - a
	ans += a * (a - 1) // 2 + b * (b - 1) // 2
ans = (n * (n + 1)) // 2 - ans
print(ans)


from math import *
#n,k=map(int,input().split())
#A = list(map(int,input().split()))
n,k = map(int,input().split())
ans = [0] * n
#^xor
lul = 2**k - 1
A = list(map(int,input().split()))
ans[0]  = A[0]
for j in range(1, n):
    ans[j] = ans[j-1]^A[j]
#print(ans)
d = dict()
for j in range(n):
    if ans[j] in d:
        d[ans[j]]+=1;
    else:
        d[ans[j]] = 1
#print(d)
ans =0
def huy(n):
    return n*(n-1)//2
for j in d:
    now = d[j]
    #print(d[j],j)
    xor = lul^j
    cur = now

    if xor in d :

        now2 = d[xor]
        #print(now,xor)
        cur += now2



        ans += huy(cur//2+cur%2)
        ans+=huy(cur//2)
        if j ==0:
            ans+=2*(cur//2)
    else:
        if(j==0 or xor ==0):
            ans+= 2*(cur//2)
        ans += 2*huy(cur // 2 + cur % 2)
        ans += 2*huy(cur // 2)
print(huy(n+1) - ans//2)

def add(num):
    if(num<=1):
        return 0
    return (num*(num-1))//2
    
    
n,k=list(map(int,input().split()))

a=list(map(int,input().split()))
pre=[a[0]]
base=(2**(k))-1
hb=2**(k-1)
for i in range(1,n):
    pre.append(a[i]^pre[-1])
    
cnt=dict()
cnt[0]=[0,0]

for i in range(n):
    if(pre[i]>=hb):
        if(base-pre[i] not in cnt):
            cnt[base-pre[i]]=[0,0]
        cnt[base-pre[i]][1]+=1
    else:
        if(pre[i] not in cnt):
            cnt[pre[i]]=[0,0]
        cnt[pre[i]][0]+=1
cnt1=0
#print(pre)
#print(cnt)
for i in list(cnt.values()):
    sum1=i[0]+i[1]
    cnt1+=add(sum1//2)
    cnt1+=add((sum1+1)//2)
cnt1+=sum(cnt[0])//2
#print(cnt1)
print((n*(n+1))//2 - cnt1)
    
    

    


from collections import defaultdict
n,k = map(int,input().split())
arr = list(map(int,input().split()))
xors = defaultdict(int)
xors[0]=1
comp = (1<<k)-1
ans = n*(n+1)//2
xor = 0
for a in arr:
	xor^=a
	if xors[xor]>xors[comp^xor]:
		xor^=comp
	ans-=xors[xor]
	xors[xor]+=1
print(ans)

n, k = [int(i) for i in input().split()]
d = dict()
d[0] = 1
x = 0
for i in [int(i) for i in input().split()]:
    x ^= i
    v = min(x, (1 << k) - x - 1)
    if v not in list(d.keys()):
        d[v] = 0
    d[v] += 1
ans = 0
for k, v in list(d.items()):
    c1 = v // 2
    c2 = v - c1
    ans += c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2
print(n * (n - 1) // 2 + n - ans)


n,k=list(map(int,input().split()))
arr=list(map(int,input().split()))
newarr=[0]

for num in arr:
  newarr+=[newarr[-1]^num]
dic={}
for num in newarr:
  x=(min(num,2**k-1-num),max(num,2**k-1-num))
  if x in dic:
    dic[x]+=1
  else:
    dic[x]=1
ans=0
for elem in dic:
  m=dic[elem]
  half=m//2
  ans+=half*(half-1)/2
  half=m-half
  ans+=half*(half-1)/2
ans=n*(n+1)/2-ans
print(int(ans))
  
    


import collections

def __starting_point():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    p = 0
    d = collections.Counter()
    d[0] = 1
    limit = 1 << (k-1)
    mask = (1 << k) - 1
    for i in range(n):
        p ^= min(a[i], mask-a[i])
        d[p] += 1

    res = 0
    for key in d:
        i = d[key] // 2
        j = d[key] - i
        res += (i-1)*i//2 + (j-1)*j//2
    res = n*(n+1)//2 - res
    print(res)
__starting_point()

n,k=map(int,input().split())
a=list(map(int,input().split()))
running=[0]
for i in range(n):
    running.append(running[-1]^a[i])
for i in range(n+1):
    if running[i]>=2**(k-1):
        running[i]=2**k-1-running[i]
running.sort()
streaks=[]
curr=1
for i in range(n):
    if running[i]==running[i+1]:
        curr+=1
    else:
        streaks.append(curr)
        curr=1
streaks.append(curr)
bad=0
for guy in streaks:
    if guy%2==0:
        bad+=(guy//2)*(guy//2-1)
    else:
        bad+=(guy//2)**2
print((n*(n+1))//2-bad)

[n, k] = [int(t) for t in input().split(' ')]
a = [int(t) for t in input().split(' ')]

mask = (1 << k) - 1

def c2(n):
    return (n * (n - 1)) // 2

count = {}
count[0] = 1

p = 0
for i in a:
    p = p ^ i
    p = min(p, p ^ mask)
    count[p] = count.get(p, 0) + 1

res = 0
for [_, cnt] in list(count.items()):
    k = cnt // 2
    res += c2(k) + c2(cnt - k)

print(c2(n + 1) - res)


# https://codeforces.com/contest/1054/problem/D
n, k = list(map(int, input().split()))
a    = list(map(int, input().split()))
p    =  [0] * (n+1)
base = (1<<k)-1 

def kC2(k):
    return (k-1) * k// 2
    
d = {}    
for i in range(1, n+1):
    p[i] = p[i-1] ^ a[i-1]
    p[i] = min(p[i] , p[i] ^ base)

    if p[i] not in d:
        d[p[i]] = 0 
    d[p[i]] += 1

if 0 not in d:
    d[0] = 0
d[0] += 1

ans   = n * (n+1) // 2
minus = 0

for k, v in list(d.items()):
    minus += kC2(v // 2) + kC2(v - v // 2)
        
print(ans - minus)    

#6 3
#1 4 4 7 3 4


'''input
3 2
1 3 0
'''
def solve():
	n,k = list(map(int,input().split()))
	flipVal = (1<<k)-1
	l = list(map(int,input().split()))
	D = {}
	D[0]=1
	for i in range(1,n):
		l[i]^=l[i-1]
	for i in range(0,n):
		l[i]=min(l[i],l[i]^flipVal)
		if l[i] in D:
			D[l[i]]+=1
		else:
			D[l[i]]=1
	#print(l)
	total = n*(n+1)//2
	bad = 0
	for i in D:
		temp = D[i]
		tot = temp//2
		bad+= tot*(tot-1)//2
		tot = temp - tot
		bad+= tot*(tot-1)//2
	print(total-bad)
	return
t = 1
#t = int(input())
while t>0:
	t-=1
	solve()

from collections import defaultdict
n,k = map(int,input().split())
arr = list(map(int,input().split()))
xors = defaultdict(int)
xors[0]=1
comp = (1<<k)-1
ans = n*(n+1)//2
xor = 0
for a in arr:
	xor^=a
	if xors[xor]>xors[comp^xor]:
		xor^=comp
	ans-=xors[xor]
	xors[xor]+=1
print(ans)