Given an array of integers arr.
We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).
Let's define a and b as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.
Return the number of triplets (i, j and k) Where a == b.
 
Example 1:
Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:
Input: arr = [1,1,1,1,1]
Output: 10

Example 3:
Input: arr = [2,3]
Output: 0

Example 4:
Input: arr = [1,3,5,7,9]
Output: 3

Example 5:
Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

 
Constraints:

1 <= arr.length <= 300
1 <= arr[i] <= 10^8

Difficulty: interview

Starter code:

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        

Solutions:
class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        res = xors = 0
        freq = collections.defaultdict(int, {0:1})
        _sum = collections.defaultdict(int)
        for i in range(n):
            xors ^= arr[i]
            res += freq[xors] * i - _sum[xors]
            freq[xors] += 1
            _sum[xors] += i+1
                
        return res
                


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        store=[0]
        n=len(arr)
        for i in range(n):
            store.append(arr[i]^store[i])
        ans=0
        print(store)
        for i in range(1,n):
            for k in range(i+1,n+1):
                if store[i-1]==store[k]:
                    ans+=(k-i)
        return ans


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        for i in range(n):
            p1 = [0]*(n+1)
            p1[i] = arr[i]
            for j in range(i+1,n):
                p1[j] = p1[j-1]^arr[j]
                p2 = [0]*(n+1)
                for k in range(j,n):
                    p2[k] = p2[k-1]^arr[k]
                    if p1[j-1] == p2[k]:
                        ans += 1
        return ans 

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        arr=[0]+arr
        res=0
        for k in range(1,len(arr)):
            arr[k]^=arr[k-1]
            for j in range(1,k+1):
                for i in range(1,j):
                    b=arr[k]^arr[j-1]
                    a=arr[j-1]^arr[i-1]
                    if a==b:
                        #print(i-1,j-1,k-1)
                        res+=1
        #print(arr)
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        res = 0
        xors = [0] * (n + 1)
        for z in range(n):
            xors[z] = xors[z-1] ^ arr[z] 
    
        for i in range(n-1):
            for j in range(i+1, n):
                for k in range(j, n):
                    a = xors[j-1] ^ xors[i-1]
                    b = xors[k] ^ xors[j-1]
                    if a == b:
                        res += 1
                
        return res
                


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        res = 0
        for i in range(1, len(arr)):
            arr[i] ^= arr[i-1]
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                for k in range(j, len(arr)):
                    if i:
                        a = arr[j-1] ^ arr[i-1]
                    else:
                        a = arr[j-1]
                    b = arr[k] ^ arr[j-1]
                    if a == b:
                        res += 1
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        ans = 0
        pool = dict()
        pool[(0,0)] = 0
        pool[(1,1)] = 0
        for i in range(len(arr)-1):
            for j in range(i+1, len(arr)):
                if (i,j) not in pool:
                    # a = reduce(lambda a, b: a^b, arr[i:j])
                    a = pool[(i,j-1)]^arr[j-1]
                    pool[(i,j)] = a
                else: 
                    a = pool[(i,j)]
                for k in range(j, len(arr)):
                    if (j,k+1) not in pool:
                        # b = reduce(lambda a, b: a^b, arr[j:k+1])
                        if j == k: 
                            b = arr[k]
                        else:
                            b = pool[(j,k)]^arr[k]
                        pool[(j,k+1)] = b
                    else:
                        b = pool[(j,k+1)]
                    if a == b: ans += 1
        return ans
                        


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        prefix = [0] * n
        prefix[0] = arr[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] ^ arr[i]
        
        ans = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                for k in range(j, n):
                    t = prefix[i - 1] if i > 0 else 0
                    if prefix[j - 1] ^ t == prefix[k] ^ prefix[j - 1]:
                        # print(i, j, k, prefix[i - 1], prefix[j - 1], prefix[k])
                        ans += 1
        return ans


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        scan = [0 for i in arr]
        scan[0] = arr[0]
        for i in range(1, len(arr)):
            scan[i] = scan[i - 1] ^ arr[i]
        res = 0
        for i in range(len(arr)-1):
            for j in range(i + 1, len(arr)):
                for k in range(j, len(arr)):
                    a = scan[j - 1] ^ scan[i] ^ arr[i]
                    b = scan[k] ^ scan[j - 1]
                    if a == b:
                        res += 1
        return res
            


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        xor = arr.copy()
        for i in range(1,len(xor)):
            xor[i] ^= xor[i-1]
        print([bin(z) for z in arr])
        print([bin(z) for z in xor])
        
        count = 0
        
        for i in range(len(arr)-1):
            for j in range(i+1,len(arr)):
                for k in range(j,len(arr)):
                    # print(i,j,k)
                    a = xor[j-1] if i == 0 else xor[j-1] ^ xor[i-1]
                    b = xor[k] ^ xor[j-1]
                    # print(a,b)
                    if a == b:
                        # print(\"xxx\")
                        count += 1
        return count
                    
                    


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        prefix = list(arr)
        for i in range(1, n):
            prefix[i] ^= prefix[i - 1]
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j, n):
                    a = prefix[j - 1] ^ prefix[i] ^ arr[i]
                    b = prefix[k] ^ prefix[j - 1]
                    ans += 1 if a == b else 0
        return ans 

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        res=0
        n=len(arr)
        for i in range(n-1):
            tmp=arr[i]
            for j in range(i+1,n):
                tmp=tmp^arr[j]
                if tmp==0:
                    res+=j-i
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        # S1
        ans, size = 0, len(arr)
        xor = [0] * size
        xor[0] = arr[0]
        for i in range(1, size):
            xor[i] = arr[i] ^ xor[i-1]
            
        for i in range(size):
            for j in range(i+1, size):
                for k in range(j, size):
                    a = xor[j-1] ^ xor[i-1] if i > 0 else xor[j-1]
                    b = xor[k] ^ xor[j-1]
                    if a == b: ans += 1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        a = []
        n = len(arr)
        for i in range(n):
            if i == 0:
                a.append(arr[i])
            else:
                a.append(arr[i] ^ a[-1])
        
        ans = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j, n):
                    x = a[j-1] ^ (0 if i == 0 else a[i-1])
                    y = a[k] ^ a[j-1]
                    if x == y:
                        ans += 1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prefix = [0 for _ in range(len(arr))]
        prefix[0] = arr[0]
        for i in range(1, len(arr)):
            prefix[i] = arr[i] ^ prefix[i-1]
        res = 0
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                for k in range(j, len(arr)):
                    a = prefix[j-1] ^ prefix[i-1] if i >= 1 else prefix[j-1]
                    b = prefix[k] ^ prefix[j-1]
                    res += (a == b)
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
        # O(N2)
        
        # prefix xor array
        
        prefix = [arr[0]]
        for i in range(1, len(arr)):
            prefix.append(prefix[-1] ^ arr[i])
        
        ans = 0
        for i in range(1, len(prefix)):
            for j in range(i+1, len(prefix)):
                if prefix[i-1]^prefix[j] == 0:
                    ans += j-i
        for i in range(len(prefix)):
            if prefix[i]==0:
                ans += i
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        N = len(arr)
        A, pre = [arr[0]], arr[0]
        for ii in arr[1:]:
            pre ^= ii
            A.append(pre)
        res = 0
        for ii in range(N):
            for kk in range(ii + 1, N):
                a_i, a_k = A[ii - 1] if ii else 0, A[kk]
                a_ik = a_k ^ a_i
                if not a_ik:
                    res += (kk - ii)
        return res
                    



class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        xors = [arr[0]]
        
        for i in range(1, len(arr)):
            xors.append(xors[-1] ^ arr[i])
            
        # 2 1 0 6 7
        print(xors)
        n = len(arr)
        count = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                temp = xors[j]
                if i > 0:
                    temp ^= xors[i - 1]
                
                if temp == 0:
                    count += j - i   
                    
        return count
                


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prefix = [0]*(len(arr)+1)
        prefix[1] = arr[0]
        res = 0
        for i in range(1, len(arr)):
            prefix[i+1] = prefix[i]^arr[i]
        print(prefix)
        for i in range(len(arr)-1):
            for j in range(i, len(arr)):
                if prefix[j+1]^prefix[i] == 0:
                    res+=(j-i)

        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        preXor = [0] * (len(arr) + 1)
        preXor[0] = arr[0]
        for i in range(1, len(arr)):
            preXor[i] = preXor[i-1] ^ arr[i]
        ret = 0
        for i in range(len(arr)-1):
            l = preXor[i-1]
            for k in range(i+1, len(arr)):
                if l == preXor[k]:
                    ret += k - i
        return ret


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        count, n = 0, len(arr)
        for i in range(n - 1):
            accu = arr[i]
            for k in range(i + 1, n):
                accu ^= arr[k]
                if accu == 0: count += k - i
        return count

class Solution:
    def allPrefixXor(self, arr: List[int]) -> List[int]:
        prefix_xor: List[int] = [0] * len(arr)
            
        prefix_xor[0] = arr[0]
        for i in range(1, len(arr)):
            prefix_xor[i] = prefix_xor[i - 1] ^ arr[i]
            
        return prefix_xor
    
    
    def allSegmentXor(self, arr: List[int]) -> List[List[int]]:
        prefix_xor: List[int] = self.allPrefixXor(arr)
        segment_xor: List[List[int]] = [[0] * len(arr) for _ in range(len(arr))]
        
        segment_xor[0] = prefix_xor[:]
        for first in range(1, len(segment_xor) - 1):
            for last in range(first + 1, len(segment_xor[first])):
                segment_xor[first][last] = prefix_xor[last] ^ prefix_xor[first - 1]

        return segment_xor
    
        
    def countTriplets(self, arr: List[int]) -> int:
        segment_xor: List[List[int]] = self.allSegmentXor(arr)
        n_triplets: int = 0
            
        for first in range(len(segment_xor) - 1):
            for last in range(first + 1, len(segment_xor[first])):
                if segment_xor[first][last] == 0:
                    n_triplets += last - first
                    
        return n_triplets

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        cumxor = [arr[0]]
        for i in range(1, n):
            cumxor.append(cumxor[i-1] ^ arr[i])
        cumxor.append(0)
        
        res = 0
        for i in range(0, n):
            for j in range(i+1, n):
                if cumxor[i-1] == cumxor[j]:
                    res += j - i
        return res


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        d = defaultdict(set)
        s = 0
        d[0].add(-1)
        for i,x in enumerate(arr):
            s ^= x
            d[s].add(i)

        return sum([abs(a-b)-1 for k in d for a,b in combinations(d[k],2)])   


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
        triplets = 0
        
        #rangeXOR[i,j] stores XOR of elements from arr[i] to arr[j] (both incl), i<j
        #rangeXOR = []
        for i, a in enumerate(arr):
            #tackle sub arrays starting at arr[i]
            subrange = []
            
            for j, b in enumerate(arr[i:]):
                j_absolute = i + j
                
                if j_absolute == i:
                    subrange.append(b)
                else:  #j_absolute > i
                    subrange.append(subrange[-1] ^ b)
                
                if subrange[-1] == 0:
                    #output all triplets here
                    triplets += j   #j_absolute - i
                    
            #rangeXOR.append(subrange)
            
        return triplets

import numpy as np

class Solution:
    def countTriplets(self, arr: List[int]) -> int:

        cumxor = [arr[0]]
        for k  in range(1, len(arr)):
            cumxor.append(cumxor[-1]^arr[k])
        counter = 0
        for x in range(1, len(arr)):
            if cumxor[x] == 0:
                counter += x
            for y in range(x):
                if cumxor[x] == cumxor[y]:
                    counter +=  x -y -1
                
        return counter
            
        


# N = len(arr)
# time: O(N^2)
# space: O(N^2)
class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        memo = [arr[:] for _ in range(len(arr))]
        for i in range(len(arr)):
            tmp = arr[i]
            for j in range(i + 1, len(arr)):
                tmp ^= arr[j]
                memo[i][j] = tmp
        return sum([(j - i) * (memo[i][j] == 0) for i in range(len(arr)) for j in range(i + 1, len(arr))])


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        arr=[0]+arr
        res=0
        for k in range(1,len(arr)):
            arr[k]^=arr[k-1]
            for i in range(1,k):
                if arr[k]^arr[i-1]==0:
                    res+=(k-i)
        #print(arr)
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        res = 0
        
        dp = [[0 for i in range(len(arr))] for j in range(len(arr))]
        
        for i in range(len(arr)):
            for j in range(i, len(arr)):
                a = 0
                # [i, j - 1]
                if j == i:
                    a = arr[i]
                else:
                    a = dp[i][j - 1] ^ arr[j]
                dp[i][j] = a
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if dp[i][j] == 0:
                    res += (j - i)
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        if len(arr) < 2:
            return 0
        xors = [i for i in arr]
        for i in range(1, len(xors)):
            xors[i] ^= xors[i - 1]
        ans = 0
        for j in range(1, len(xors)):
            cnt = Counter([xors[j - 1]^xors[i - 1] for i in range(1, j)])
            cnt[xors[j - 1]] = cnt.get(xors[j - 1], 0) + 1
            for k in range(j, len(xors)):
                ans += cnt.get(xors[k]^xors[j - 1], 0)
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        count = 0
        for j in range(1, n):
            right_xor = collections.defaultdict(int)
            curr_xor = 0
            for k in range(j, n):
                curr_xor ^= arr[k]
                right_xor[curr_xor] += 1
            curr_xor = 0
            for i in range(j-1, -1, -1):
                curr_xor ^= arr[i]
                if curr_xor in right_xor:
                    count += right_xor[curr_xor]
        return count

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        @lru_cache(None)
        def xor_reduce(i,j):
            if j - i == 1: return arr[i]^arr[j]
            else:
                return xor_reduce(i+1,j) ^ arr[i]

        ans = 0
        N = len(arr)
        for i in range(N):
            for j in range(i+1,N):
                x = xor_reduce(i,j)
                if x == 0:
                    ans += (j-i)
        return ans
        


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        from collections import defaultdict as dd
        n=len(arr)
        cnt=0
        dp=[[-1]*n for i in range(n)]
        for i in range(n):
            curr=arr[i]
            dp[i][i]=curr
            for j in range(i+1,n):
                curr=curr^arr[j]
                dp[i][j]=curr
        for i in range(1,n):
            map=dd(int)
            for j in range(i):
                map[dp[j][i-1]]+=1
            for j in range(i,n):
                cnt+=map[dp[i][j]]
                if(map[dp[i][j]]==0):del map[dp[i][j]]
        return cnt

from collections import defaultdict as dd
class Solution:
    def countTriplets(self,a):
        n=len(a)
        cnt=0
        dp=[[-float('inf')]*n for i in range(n)]
        for i in range(n):
            curr=a[i]
            dp[i][i]=curr
            for j in range(i+1,n):
                curr=curr^a[j]
                dp[i][j]=curr
        for i in range(1,n):
            map=dd(int)
            for j in range(i):
                map[dp[j][i-1]]+=1
            for j in range(i,n):
                cnt+=map[dp[i][j]]
                if(map[dp[i][j]]==0):del map[dp[i][j]]
        return cnt

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        d = defaultdict(list)
        d[0].append(-1)
        cur, rst = 0, 0
        for i, a in enumerate(arr):
            cur ^= a
            if i > 0:
                for j in d[cur]:
                    rst += i-j-1
            d[cur].append(i)
        return rst

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        for i in range(1, n):
            l = Counter()
            a = 0
            for j in range(i-1, -1, -1):
                a ^= arr[j]
                l[a] += 1
            a = 0
            for j in range(i, n):
                a ^= arr[j]
                ans += l[a]
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        #0 <= i < j < k <= n
        #xor(arr[i:j]) == xor[j:k]
        d = {}
        xormat = [[0] * (n+1) for i in range(n)]
        for i in range(n):
            for j in range(i+1, n+1):
                xormat[i][j] = v = xormat[i][j-1] ^ arr[j-1]
                if v in d:
                    d[v].append((i,j))
                else:
                    d[v] = [(i, j)]
        count = 0
        #print(d)
        from collections import defaultdict
        for values in list(d.values()):
            counts = defaultdict(list)
            for i, j in values:
                counts[i].append(j)
            for v in values:
                count += len(counts[v[1]])
        return count


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        values = {}
        for i in range(len(arr)):
            val = 0
            for j in range(i, len(arr)):
                val ^= arr[j]
                if val not in values:
                    values[val] = {
                        'start': {},
                        'end': {}
                    }
                if i not in values[val]['start']:
                    values[val]['start'][i] = 0
                values[val]['start'][i] += 1
                if j not in values[val]['end']:
                    values[val]['end'][j] = 0
                values[val]['end'][j] += 1
        
        total = 0
        
        for val in values:
            for index in values[val]['end']:
                if index + 1 in values[val]['start']:
                    total += values[val]['start'][index + 1] * values[val]['end'][index]
        
        return total


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        ans, n = 0, len(arr)
        xors = [0]*(n+1)
        for i in range(1, n+1):
            xors[i] = xors[i-1] ^ arr[i-1]
        for i in range(n):
            for k in range(i+1, n):
                if xors[k+1] ^ xors[i] != 0:
                    continue
                for j in range(i+1, k+1):
                    if xors[j] ^ xors[i] == xors[k+1] ^ xors[j]:
                        ans += 1
        return ans


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        prefixes = [arr[0]]
        result = 0

        for i in range(1, n):
            prefixes.append(arr[i] ^ prefixes[-1])

        for i in range(n - 1):
            for k in range(i + 1, n):
                sub_array_xor = prefixes[k] if i == 0 else prefixes[k] ^ prefixes[i - 1]
                if sub_array_xor == 0:
                    for j in range(i + 1, k + 1):
                        left_part = prefixes[j -
                                             1] if i == 0 else prefixes[j-1] ^ prefixes[i - 1]
                        right_part = prefixes[k] ^ prefixes[j-1]
                        if left_part == right_part:
                            result += 1

        return result

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        preXor = [0] * (len(arr) + 1)
        preXor[0] = arr[0]
        for i in range(1, len(arr)):
            preXor[i] = preXor[i-1] ^ arr[i]
        ret = 0
        for i in range(len(arr)-1):
            for j in range(i+1, len(arr)):
                l = preXor[i-1]
                for k in range(j, len(arr)):
                    #print(i, j, k)
                    if l == preXor[k]:
                        #print(\"match:\", i, j, k)
                        ret += 1
        return ret


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
        def xor(arr):
            xor = 0
            for a in arr:
                xor^=a
            return xor
        
        result = 0
        for i in range(0,len(arr)):
            for j in range(i+1,len(arr)):
                if xor(arr[i:j+1]) == 0:
                    result += j-i
        return result
                    
            


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        N = len(arr)
        ans = 0
        for i in range(N-1):
            v = arr[i]
            l = [v]
            for k in range(i+1, N):
                v ^= arr[k]
                for w in l:
                    if v ^ w == w:
                        ans += 1
                l.append(v)
        return ans

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        res = cur = 0
        count = {0: [1, 0]}
        for i, a in enumerate(A):
            cur ^= a
            n, total = count.get(cur, [0, 0])
            res += i * n - total
            count[cur] = [n + 1, total + i + 1]
        return res
            
            


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        N = len(arr)
        ans = 0
        for i in range(N-1):
            v = arr[i]
            l = [v]
            for k in range(i+1, N):
                v ^= arr[k]
                for w in l:
                    if v ^ w == w:
                        ans += 1
                l.append(v)
        return ans
    
        # there's an O(N) algorithm


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        ans=0
        print(len(arr[:-1]))
        for key1 in range(len(arr[:-1])):
            a=0
            for key2,j in enumerate(arr[key1:]):
                a^=j
                b=0
                for k in arr[key2+key1+1:]:
                    b^=k
                    if(b==a):
                        ans+=1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 2:
          return 0
        out = 0
        for i in range(n -1):
          a = arr[i]
          for j in range(i+1, n):
            b = 0
            for k in range(j, n):
              b ^= arr[k]
              # print(i, j, k, a == b)
              if a == b:
                out += 1
            a ^= arr[j]

        return out

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
    
        count=0
        n=len(arr)
        for i in range(n-1):
            x=arr[i]
            for j in range(i+1,n):
                y=0
                for k in range(j,n):
                    y=y^arr[k]
                    if x==y:
                        count+=1
                x=x^arr[j]
                
        return count
                    
                    
                    


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        c = 0
        for k in range(1,n):
            b=0
            for j in range(k, 0, -1):
                b = b^arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a = a^arr[i]
                    if a==b:
                        c+=1
        return c
                    


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        '''n = len(arr)
        count = 0
        for i in range(n-1):
            for j in range(i+1, n):
                a = arr[i]
                for x in range(i+1, j):
                    a ^= arr[x]
                for k in range(j, n):
                    b = arr[j]
                    for x in range(j+1, k+1):
                        b ^= arr[x]
                    if a == b:
                        count+=1
        return count'''
        n = len(arr)
        c = 0
        for k in range(1,n):
            b=0
            for j in range(k, 0, -1):
                b = b^arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a = a^arr[i]
                    #print(i, j, k, \"=>\", a, b)
                    if a==b:
                        c+=1
        return c

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        count = 0
        for k in range(len(arr)):
            b = 0
            for j in range(k, 0, -1):
                b = b^arr[j] 
                a = 0
                for i in range(j-1, -1, -1):
                    a = a^arr[i]
                    if a == b:
                        count +=1
                      
        return count

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        count=0
        for i in range(len(arr)):
            
            a=arr[i]
            for j in range(i+1,len(arr)):
                a=a^arr[j]
                b=arr[j]
                for k in range(j,len(arr)):
                    b=b^arr[k]
                    if a==b:
                        count+=1
        return count

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
#         ans = 0
#         n = len(arr)

#         for i in range(n-1):
            
#             left, right = arr[i], 0

#             for j in range(i + 1, n):
        
#                 right ^= arr[j]
                
#                 if left == right:
#                     ans += (j - i)

#         return ans

        n = len(arr)
        c = 0
        for k in range(1,n):
            b=0
            for j in range(k, 0, -1):
                b = b^arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a = a^arr[i]
                    #print(i, j, k, \"=>\", a, b)
                    if a==b:
                        c+=1
        return c


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        count = 0
        for k in range(1, len(arr)):
            b = 0
            for j in range(k, 0, -1):
                b = b^arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a = a ^ arr[i]
                    if a == b:
                        count += 1
        return count


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        c = 0
        for k in range(1,n):
            b=0
            for j in range(k, 0, -1):
                b = b^arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a = a^arr[i]
                    if a==b:
                        c+=1
        return c

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
        n = len(arr)
        res = 0
        for i in range(n):
            a = 0
            for j in range(i+1, n):
                a ^= arr[j-1]
                b = 0
                for k in range(j, n):
                    b ^= arr[k]
                    if a == b:
                        res += 1
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        count = 0
        
        if len(arr) < 2:
            return count
        
        for i in range(len(arr)):
            a = 0
            for j in range(i, len(arr) - 1):
                a ^= arr[j]
                b = 0
                for k in range(j + 1, len(arr)):
                    b ^= arr[k]

                    if a == b:
                        count += 1

                        
        return count


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        xor = arr.copy()
        for i in range(1,len(xor)):
            xor[i] ^= xor[i-1]
        print([bin(z) for z in arr])
        print([bin(z) for z in xor])
        
        count = 0
        
        for i in range(len(arr)-1):
            for j in range(i+1,len(arr)):
                a = xor[j-1] if i == 0 else xor[j-1] ^ xor[i-1]
                b = 0
                for k in range(j,len(arr)):
                    # print(i,j,k)
                    # b = xor[k] ^ xor[j-1]
                    b ^= arr[k]
                    # print(a,b)
                    if a == b:
                        # print(\"xxx\")
                        count += 1
        return count
                    
                    


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        l = len(arr)
        if l==1:
            return 0
        mat = [[0 for i in range(l)] for i in range(l)]
        
        for i in range(l-1):
            mat[i][i+1] = arr[i]^arr[i+1]
            for j in range(i+2,l):
                mat[i][j] = mat[i][j-1]^arr[j]
        # print(mat)
        count = 0
        
        for i in range(l-1):
            for j in range(i+1,l):
                curr = mat[i][j-1]
                if i+1==j:
                    curr = arr[i]
                for k in range(j,l):
                    pres = mat[j][k]
                    if j==k:
                        pres= arr[j]
                    if curr == pres:
                        count+=1
                
        return count


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        l = len(arr)
        if l==1:
            return 0
        mat = [[0 for i in range(l)] for i in range(l)]
        
        for i in range(l-1):
            mat[i][i+1] = arr[i]^arr[i+1]
            for j in range(i+2,l):
                mat[i][j] = mat[i][j-1]^arr[j]
        # print(mat)
        count = 0
        
        for i in range(l):
            for j in range(i+1,l):
                curr = mat[i][j-1]
                if i+1==j:
                    curr = arr[i]
                for k in range(j,l):
                    # print(i,j,k)
                    
                    pres = mat[j][k]
                    if j==k:
                        pres= arr[j]
                    # if i==0 and j==2 and k==2:
                        # print(\"curr \",curr)
                        # print(\"pres \",pres)
                    if curr == pres:
                        count+=1
                        # print(\"counted\")
                
        return count


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        res = 0
        for i in range(len(arr) - 1):
            accu = arr[i]
            for k in range(i + 1, len(arr)):
                accu ^= arr[k]
                if not accu:
                    res += k - i
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prefix_xor = [arr[0]]
        answer = 0
        
        for i in range(1, len(arr)):
            prefix_xor.append(prefix_xor[i-1] ^ arr[i])
        
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                
                a = prefix_xor[j]
                
                if i > 0:
                    a = a ^ prefix_xor[i-1]
                
                for k in range(j, len(arr)):
                    b = prefix_xor[k] ^ prefix_xor[j]
                    
                    if a == b:
                        answer += 1
                        
        return answer

class Solution:
    def countTriplets(self, a: List[int]) -> int:
        p = [a[0]]
        for i in range(1,len(a)):
            p.append(p[-1]^a[i])
        # d=dict()
        ans = 0
        # print(p)
        for i in range(len(a)-1):
            for j in range(i+1,len(a)):
                v = p[j]^p[i]^a[i]
                for k in range(j,len(a)):
                    vv= p[k]^p[j]
                    if v==vv:
                        # print(i,j,k)
                        ans+=1
        #         v = p[j]^p[i]
        #         if v not in d:
        #             d[v] = list()
        #         d[v].append((i,j))
        # for i in d:
        #     d[i].sort()
        # print(d)
        # for i in d:
        #     for x in range(1,len(d[i])):
        #         if abs(d[i][x][0]-d[i][x-1][1])<=1:
        #             ans +=1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        res = 0
        xors = [0] * (n + 1)
        for z in range(n):
            xors[z] = xors[z-1] ^ arr[z] 
    
        for i in range(n - 1):
            for j in range(i + 1, n):
                for k in range(j, n):
                    if xors[i - 1] ^ xors[k] == 0:
                        res += 1
                
        return res
                


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        xor=[[0]*len(arr) for _ in range(len(arr))]
        for i in range(len(arr)):
            for j in range(i,len(arr)):
                if j==i:
                    xor[i][j]=arr[j]
                else:
                    xor[i][j]=xor[i][j-1]^arr[j]
        ans=0
        for i in range(len(arr)-1):
            for j in range(i+1,len(arr)):
                for k in range(j,len(arr)):
                    if xor[i][j-1]==xor[j][k]:
                        ans+=1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        ans, n = 0, len(arr)
        xors = [0]*(n+1)
        for i in range(1, n+1):
            xors[i] = xors[i-1] ^ arr[i-1]
        for i in range(n):
            for j in range(i+1, n):
                a = xors[j] ^ xors[i]
                for k in range(j, n):
                    if a == xors[k+1] ^ xors[j]:
                        ans += 1
        return ans


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        l = len(arr)
        count = 0
        for k in range(1,l):
            b=0
            for j in range(k, 0, -1):
                b^=arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a^=arr[i]
                    if a==b:
                        count+=1
        return count

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        res = 0
        xors = [0] * (n + 1)
        for z in range(n):
            xors[z] = xors[z-1] ^ arr[z] 
    
        for i in range(n - 1):
            for j in range(i + 1, n):
                for k in range(j, n):
                    if xors[i - 1]^ xors[k] == 0:
                        res += 1
                
        return res
                


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
      start = arr[0]
      res = 0
      for i in range(1, len(arr)):
        start ^= arr[i]
        arr[i] = start
      arr = [0] + arr
      for i in range(1,len(arr)):
        for j in range(i+1, len(arr)):
          first_part = arr[j-1] ^ arr[i-1]
          for k in range(j, len(arr)):
            second_part = arr[k] ^ arr[j-1]
            if first_part == second_part:
              res += 1
              #print (i,j,k)
      return res


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        xor = arr.copy()
        for i in range(1,len(xor)):
            xor[i] ^= xor[i-1]
        print([bin(z) for z in arr])
        print([bin(z) for z in xor])
        
        count = 0
        
        for i in range(len(arr)-1):
            for j in range(i+1,len(arr)):
                a = xor[j-1] if i == 0 else xor[j-1] ^ xor[i-1]
                for k in range(j,len(arr)):
                    # print(i,j,k)
                    b = xor[k] ^ xor[j-1]
                    # print(a,b)
                    if a == b:
                        # print(\"xxx\")
                        count += 1
        return count
                    
                    


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        # prefix_arr=[]
        n=len(arr)
        for i in range(1,n):
            arr[i]^=arr[i-1]
        out=0
        for i in range(n):
            if arr[i]==0:
                out+=i
            for j in range(i+1,n):
                if arr[i]==arr[j]:
                    out+=j-i-1
        return out
                
        


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        # worst case is iterate from i -> j -> k and k -> arr.length and test out each comb
        # compute i -> j - 1, keep counter for each i, j comb
        # compute j -> k
        # for each i -> j,
        count = 0
        for i in range(1, len(arr)):
            arr[i] ^= arr[i - 1]
        for i in range(0, len(arr) - 1):
            for j in range(i + 1, len(arr)):
                target = arr[j - 1]
                if i > 0:
                    target ^= arr[i - 1]
                for k in range(j, len(arr)):
                    curr = arr[k]
                    curr ^= arr[j - 1]
                    if curr == target:
                        count += 1
        return count

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        # store=[0]
        # n=len(arr)
        # for i in range(n):
        #     store.append(arr[i]^store[i])
        # ans=0
        # print(store)
        # for i in range(1,n):
        #     for k in range(i+1,n+1):
        #         if store[i-1]==store[k]:
        #             ans+=(k-i)
        # print(7^6)
        # return ans
        n = len(arr)
        c = 0
        for k in range(1,n):
            b=0
            for j in range(k, 0, -1):
                b = b^arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a = a^arr[i]
                    #print(i, j, k, \"=>\", a, b)
                    if a==b:
                        c+=1
        return c

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[0]*n for i in range(n)]

        for i in range(n):
            dp[i][i] = arr[i]

        for i in range(n-1,-1,-1):
            for j in range(i+1,n):
                dp[i][j] = dp[i][j-1]^arr[j]

        output = 0
        for i in range(n-1,-1,-1):
            for j in range(i+1,n):
                for k in range(i+1,j+1):
                    if dp[i][k-1] == dp[k][j]:
                        output += 1

        return output


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        preXor = [0] * (len(arr) + 1)
        preXor[0] = arr[0]
        for i in range(1, len(arr)):
            preXor[i] = preXor[i-1] ^ arr[i]
        ret = 0
        for i in range(len(arr)-1):
            for j in range(i+1, len(arr)):
                l = preXor[j-1] ^ preXor[i-1]
                for k in range(j, len(arr)):
                    #print(i, j, k)
                    if l == preXor[k] ^ preXor[j-1]:
                        #print(\"match:\", i, j, k)
                        ret += 1
        return ret


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        c = 0
        for k in range(1,n):
            b=0
            for j in range(k, 0, -1):
                b = b^arr[j]
                a = 0
                for i in range(j-1, -1, -1):
                    a = a^arr[i]
                    #print(i, j, k, \"=>\", a, b)
                    if a==b:
                        c+=1
        return c

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        store=[0]
        n=len(arr)
        for i in range(n):
            store.append(arr[i]^store[i])
        ans=0
        for i in range(1,n):
            for k in range(i+1,n+1):
                if store[i-1]==store[k]:
                    ans+=k-i
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        prefix_xor = [0]+arr
        for i in range(1,n+1):
            prefix_xor[i] = prefix_xor[i]^prefix_xor[i-1]
        res = 0
        for i in range(n-1):
            for k in range(i+1,n):
                for j in range(i+1,k+1):
                    if prefix_xor[k+1]^prefix_xor[j] == prefix_xor[j]^prefix_xor[i]:
                        res += 1
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        ps = [0] * (n + 1)
        for i in range(n):
            ps[i + 1] = ps[i] ^ arr[i]
        res = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                for k in range(j, n):
                    if ps[i] ^ ps[j] == ps[j] ^ ps[k + 1]:
                        res += 1
        return res


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        ans = 0

        for i in range(len(arr)-1):

            for k in range(len(arr)-1, i, -1):
                if k == len(arr)-1:
                    B = arr[k]

                    for z in range(k-1, i, -1):
                        B ^= arr[z]

                    b = B
                    # print(\"[A] Bitwise for: {} = {}\".format(arr[i+1: len(arr)], b))

                else:
                    B ^= arr[k+1]
                    b = B

                    # print(\"[B] Bitwise for: {} = {}\".format(arr[i+1: k+1], b))

                a = arr[i]


                for j in range(i+1, k+1):
                    # print(j)
                    a ^= arr[j]
                    b ^= arr[j]


                    if a == b:
                        # print(\"[ans] {} {} {}\".format(i, j, k))
                        ans += 1

                    # else:
                    #     print(\"[term] {} {} {}\".format(i, j, k))


        return ans


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        xor = [0 for i in range(n+1)]
        for i in range(n):
            xor[i+1] = xor[i] ^ arr[i]
        
        ans = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j, n):
                    # print(i, j, k)
                    if xor[i]^xor[j] == xor[j]^xor[k+1]:
                        ans += 1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        s = [0] * (len(arr) + 1)
        for i in range(1, len(arr) + 1):
            s[i] = s[i - 1] ^ arr[i - 1]
        ans = 0
        # print(s)
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                for k in range(j, len(arr)):
                    # print(i, j, k,  s[k + 1] ^ s[j], s[j] ^ s[i])
                    if s[k + 1] ^ s[j] == s[j] ^ s[i]:
                        ans += 1
        return ans

from collections import defaultdict
class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        x = [0]
        for t in arr:
            x.append(x[-1]^t)
        ans = 0
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j,n):
                    if x[j]^x[i] == x[k+1]^x[j]:
                        ans+=1
        
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        psum = [0] * (n+1)
        for i in range(n):
            psum[i+1] = arr[i] ^ psum[i]
        res = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j,n):
                    a = psum[j] ^ psum[i]
                    b = psum[k+1] ^ psum[j]
                    if a == b: res += 1
        return res

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        cum = [0]
        for n in arr:
            cum.append(cum[-1]^n)
        ans=0
        for i in range(0, len(arr)-1):
            for k in range(i+1, len(arr)):
                for j in range(i+1, k+1):
                    if cum[i]^cum[j] == cum[k+1]^cum[j]:
                        ans += 1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        # worst case is iterate from i -> j -> k and k -> arr.length and test out each comb
        # compute i -> j - 1, keep counter for each i, j comb
        # compute j -> k
        # for each i -> j,
        cum = [0]
        for n in arr:
            cum.append(cum[-1]^n)
        ans=0
        for i in range(0, len(arr)-1):
            for k in range(i+1, len(arr)):
                for j in range(i+1, k+1):
                    if cum[i]^cum[j] == cum[k+1]^cum[j]:
                        ans += 1
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        c = 0
        xor = 0
        for i in range(n-1):
            xor = arr[i]
            for j in range(i+1,n):
                xor^=arr[j]
                if xor == 0:
                    c+=(j-i)
        return c


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
        
        preXor = [0] * (len(arr)+1)
        
        for i, element in enumerate(arr):  
            preXor[i + 1] = preXor[i] ^ element
        
        count = 0
        for i in range(len(arr)):
            
            for j in range(i+1, len(arr)):
                
                for k in range(j, len(arr)):
                    
                    a = preXor[j] ^ preXor[i]
                    
                    b = preXor[k+1] ^ preXor[j]
                    
                    if a == b:
                        count+=1
        
        return count


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prefixSum = [0] * (len(arr) + 1)
        for i, v in enumerate(arr):
            prefixSum[i+1] = prefixSum[i] ^ v
            
        ans = 0
        for i in range(1, len(prefixSum)):
            for j in range(i+1, len(prefixSum)):
                for k in range(j, len(prefixSum)):
                    if prefixSum[i-1]^prefixSum[j-1] == prefixSum[j-1]^prefixSum[k]:
                        # print(i-1, j-1, k-1)
                        ans += 1
        
        return ans

class Solution:
    def countTriplets(self, arr: List[int]) -> int:   
        def get_triplets(nums):
            n = len(nums)
            triplets = 0
            i = 0
            while i < n - 1:
                lsum = nums[i]
                j = i + 1
                while j < n:
                    k = j
                    rsum = nums[j]
                    while k < n:
                        if lsum == rsum: triplets += 1
                        k += 1
                        if k < n: rsum = rsum ^ nums[k]
                    j += 1
                    lsum = lsum ^ nums[j - 1]
                i += 1
            
            return triplets
        
        return get_triplets(arr)


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        xorarr = [arr[0]]
        for i in range(1, n):
            xorarr.append(xorarr[-1]^arr[i])
            
        count = 0
        
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j, n):
                    if xorarr[k]^xorarr[j-1] == xorarr[j-1]^(xorarr[i-1] if i>0 else 0):
                        #print(i, j, k)
                        count += 1
        return count


from itertools import accumulate

class Solution:
  def countTriplets(self, nums: List[int]) -> int:
    n, x = len(nums), list(accumulate(nums, lambda x, y: x ^ y, initial=0))
    count = 0
    for i in range(1, n + 1 - 1):
      for j in range(i + 1, n + 1):
        for k in range(j + 0, n + 1):
          if x[i - 1] ^ x[j - 1] == x[j - 1] ^ x[k]:
            count += 1
    return count

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prexor = [0]
        for num in arr: prexor.append(prexor[-1]^num)
        
        # print(prexor)
        cnt = 0
        # result = []
        for i in range(1,len(arr)+1):
            for j in range(i+1, len(arr)+1):
                for k in range(i+1, j+1):
                    if prexor[k-1]^prexor[i-1] == prexor[j]^prexor[k-1]: 
                        # result.append([i-1, k-1, j-1])
                        cnt+=1
        # print(result)
        return cnt

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        
        if not arr:
            return 0
        
        x=[0,arr[0]]
        for i in range(1,len(arr)):
            x.append(x[-1]^arr[i])
           
        cnt=0
        for i in range(1,len(x)):
            for j in range(i+1,len(x)):
                for k in range(j,len(x)):
                    if x[j-1]^x[i-1]==x[k]^x[j-1]:
                        cnt+=1
        return cnt

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        prefixxor = [0]

        for i in range(n):
            prefixxor.append(prefixxor[- 1] ^ arr[i])
            
#       so   arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1] = prefixxor[j - 1] ^ prefixxor[i - 1]
        count = 0
        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                for k in range(j, n + 1):
                    if prefixxor[j - 1] ^ prefixxor[i - 1] == prefixxor[k] ^ prefixxor[j - 1]:
                        count += 1
        return count