Problem:
 Score : 400 points    Problem Statement There are two persons, numbered 0 and 1 , and a variable x whose initial value is 0 .
The two persons now play a game.
The game is played in N rounds. The following should be done in the i -th round ( 1 \leq i \leq N ):   Person S_i does one of the following:  Replace x with x \oplus A_i , where \oplus represents bitwise XOR.  Do nothing.     Person 0 aims to have x=0 at the end of the game, while Person 1 aims to have x \neq 0 at the end of the game.  Determine whether x becomes 0 at the end of the game when the two persons play optimally.  Solve T test cases for each input file.      Constraints  1 \leq T \leq 100  1 \leq N \leq 200  1 \leq A_i \leq 10^{18}  S is a string of length N consisting of 0 and 1 .  All numbers in input are integers.         Input Input is given from Standard Input in the following format.
The first line is as follows:  T   Then, T test cases follow.
Each test case is given in the following format:  N  A_1  A_2  \cdots  A_N  S       Output For each test case, print a line containing 0 if x becomes 0 at the end of the game, and 1 otherwise.        Sample Input 1 3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000      Sample Output 1 1
0
0  In the first test case, if Person 1 replaces x with 0 \oplus 1=1 , we surely have x \neq 0 at the end of the game, regardless of the choice of Person 0 .  In the second test case, regardless of the choice of Person 1 , Person 0 can make x=0 with a suitable choice.

Solution (Python):
T=int(input())

def standardize(x,base_set):
  base_list=sorted(base_set,reverse=True)
  for base in base_list:
    x=min(x,x^base)    
  return x

for _ in range(T):
  N=int(input())
  alist=list(map(int,input().split()))
  slist=list(map(int,input()))
  
  base_set=set()
  for index in reversed(range(N)):
    norm_a=standardize(alist[index],base_set)
    if slist[index]==0:
      base_set.add(norm_a)
    else:
      if norm_a>0:
        print(1)
        break
    
  else:
    print(0)

Solution (Python):


t = int(input())
scale = 64

double = [2**d for d in range(scale)]
double.reverse()
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    base = [0 for _ in range(scale)]
    for i in range(n)[::-1]:
        now = a[i]
        for d in range(scale):
            if now & double[d]:
                if base[d]:
                    now ^= base[d]
                else:
                    base[d] = now
                    break
        else:
            continue
        if s[i] == '1':
            print(1)
            break
    else:
        print(0)

Solution (Python):
T = int(input())

def hakidasi(L):
  n = len(bin(max(L))) - 2
  k, end = 0, len(L)
  for i in range(n - 1, -1, -1):
    for j in range(k, end):
      if (L[j] >> i) & 1:
        L[k], L[j] = L[j], L[k]
        break
    else:
      continue
    k += 1
    for j in range(end):
      if j == k - 1: continue
      if (L[j] >> i) & 1:
        L[j] ^= L[k - 1]
  return L

def judge(L, x):
  if L == []:
    return False
  n = len(bin(max(L))) - 2
  m = len(L)
  for i in range(m):
    a = len(bin(x))
    b = len(bin(L[i]))
    if a == b:
      x ^= L[i]
    elif a > b:
      return False
    if x == 0:
      return True
  return False

def main():
  N = int(input())
  A = list(map(int, input().split()))
  S = input()
  U = 60
  
  L = []
  for i in range(N - 1, -1, -1):
    if A[i] == 0:
      continue
    n = int(S[i])
    if n == 0:
      L.append(A[i])
      L = hakidasi(L)
      if L[-1] == 0:
        L.pop()
    else:
      m = judge(L, A[i])
      if m == False:
        return 1
  return 0

for i in range(T):
  print(main())

Solution (Python):
def solve():
    base = []
    for a, s in zip(A[::-1], S[::-1]):
        
        
        
        x = a
        for y in sorted(base, reverse=True):
            x = min(x, x ^ y)
        if x:
            if s == "0":
                base.append(x)
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    
    print(solve())

Solution (Python):
def solve():
    base = [] 
    for a, s in zip(A[::-1], S[::-1]):
        
        
        

       
        x = a
        for y in base:
            x = min(x, x ^ y)

        
        if x:
            if s == "0":
                
                base.append(x)
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    
    print(solve())

Solution (Python):
for _ in range(int(input())):
    N=int(input())
    A=list(map(int,input().split()))
    S=input()
    base=[]
    for i in range(N-1,-1,-1):
        a=A[i]
        for b in base:
            test=a^b
            if a>test:
                a=test
        if a!=0:
            if S[i]=="1":
                print("1")
                break
            else:
                base.append(a)
    else:
        print("0")

Solution (Python):
def solve():
    base = []
    for a, s in zip(A[::-1], S[::-1]):
        x = a
        for y in base:
            x = min(x, x ^ y)
        if s == "0":
            if x:
                base.append(x)
        else:
            if x:
                return 1
    return 0


t = int(input())
for i in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    print(solve())

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def gauss_jordan(A, extended=False):
    """ ガウス・ジョルダン法(連立方程式の解) """

    N, M = len(A), max(A).bit_length()
    res = A[:]
    rank = 0
    for col in range(M):
        if extended and col == M-1:
            break
        pivot = -1
        for row in range(rank, N):
            if res[row]>>col & 1:
                pivot = row
                break
        if pivot == -1:
            continue
        res[rank], res[pivot] = res[pivot], res[rank]
        for row in range(N):
            if row != rank and res[row]>>col & 1:
                res[row] ^= res[rank]
        rank += 1
    
    for row in range(rank, N):
        if res[row]>>(M-1) & 1:
            return (-1, [])
    return (rank, res)

for _ in range(INT()):
    N = INT()
    A = LIST()
    S = input()
    M = max(A).bit_length()

    mat = [0] * M
    collen = 1
    for i in range(N-1, -1, -1):
        
        if S[i] == '0':
            for k in range(M):
                mat[k] |= (A[i]>>k & 1) << collen
            collen += 1
        
        else:
            cur = mat[:]
            for k in range(M):
                cur[k] |= (A[i]>>k & 1) << collen
            
            rank, res = gauss_jordan(cur, extended=True)
            if rank == -1:
                print(1)
                break
    else:
        print(0)

Solution (Python):
T = int(input())

for _ in [0]*T:
    N = int(input())
    *A, = map(int,input().split())
    S = input()

    B = []
    ans = 0
    for s,a in zip(S[::-1],A[::-1]):
        if s=="0":
            B.append(a)
        else:
            
            C = B[:]
            for i in range(64):
                for b in C:
                    if (b >> i) & 1 == 1: break
                else:
                    continue
                if (a >> i) & 1 == 1: a ^= b
                for j,c in enumerate(C):
                    if (c >> i) & 1 == 1: C[j] ^= b
            if a!=0:
                ans = 1
                break
    print(ans)

Solution (Python):
def main():
    t = int(input())
    for _ in range(t):
        n, a, s, m = int(input()), list(map(int, input().split())), input(), []
        for i in range(n-1, -1, -1):
            ans = a[i]
            for j in m:
                ans = min(ans, ans ^ j)
            if s[i] == "0":
                if ans:
                    m.append(ans)
            else:
                if ans:
                    print(1)
                    break
        else:
            print(0)


main()

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def deepcopy(li): return [x[:] for x in li]

def gauss_jordan(A, extended=False):
    """ ガウス・ジョルダン法(連立方程式の解) """

    N, M = len(A), max(A).bit_length()
    B = A[:]
    rank = 0
    res = []
    for col in range(M):
        if extended and col == M-1:
            break
        pivot = -1
        for row in range(rank, N):
            if B[row]>>col & 1:
                pivot = row
                break
        if pivot == -1:
            continue
        B[rank], B[pivot] = B[pivot], B[rank]
        for row in range(N):
            if row != rank and B[row]>>col & 1:
                B[row] ^= B[rank]
        res.append(col)
        rank += 1
    for row in range(rank, N):
        if B[row]>>(M-1) & 1:
            return (-1, [])
    return (rank, res)

for _ in range(INT()):
    N = INT()
    A = LIST()
    S = input()
    M = max(A).bit_length()

    mat = [0] * M
    collen = 1
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            for k in range(M):
                mat[k] |= (A[i]>>k & 1) << collen
            collen += 1
        else:
            cur = mat[:]
            for k in range(M):
                cur[k] |= (A[i]>>k & 1) << collen
            rank, res = gauss_jordan(cur, extended=True)
            if rank == -1:
                print(1)
                break
    else:
        print(0)

Solution (Python):
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    list0 = [0] * 64
    ans = 0

    for a, s in zip(reversed(A), reversed(S)):
        while a:
            b = a.bit_length() - 1
            if list0[b]:
                a ^= list0[b]
            else:
                if s == '1':
                    ans = 1
                else:
                    list0[b] = a

                break

        if ans: break

    print(ans)

Solution (Python):
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    list0 = [0] * 64
    ans = 0

    for a, s in zip(A[::-1], S[::-1]):
        while a:
            b = a.bit_length() - 1
            if list0[b]:
                a ^= list0[b]
            else:
                if s == '1':
                    ans = 1
                else:
                    list0[b] = a

                break

        if ans: break

    print(ans)

Solution (Python):
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    list0 = [0] * 64

    for a, s in zip(A[::-1], S[::-1]):
        if s == '1':
            while a:
                b = a.bit_length() - 1
                if list0[b]:
                    a ^= list0[b]
                else:
                    break

            if a:
                ans = 1
                break

        else:
            while a:
                b = a.bit_length() - 1
                if list0[b]:
                    a ^= list0[b]
                else:
                    list0[b] = a
                    break

    else:
        ans = 0

    print(ans)

Solution (Python):
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    if S[-1] == '1':
        print(1)
        continue

    list0 = [0] * 64

    for a, s in zip(A[::-1], S[::-1]):
        blen = a.bit_length()
        for i in range(blen, 0, -1):
            if a.bit_length() < i: continue
            if list0[i - 1]:
                a ^= list0[i - 1]
                if a == 0: break

        else:
            if s == '1':
                ans = 1
                break
            else:
                list0[a.bit_length() - 1] = a

    else:
        ans = 0

    print(ans)

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()

    ans = 0
    B = []
    for i in range(N)[::-1]:
        a = A[i]
        for b in B:
            a = min(a, a ^ b)
        if a:
            if S[i] == '1':
                ans = 1
                break
            B.append(a)
    print(ans)

Solution (Python):
def xor_battle(N, A, S):
    bit = [0] * 64
    
    for i in reversed(range(N)):
        Ai, Si = A[i], S[i]
        while Ai:
            n = Ai.bit_length() -1
            if bit[n] == 0 and Si == '1':
                return 1 
            elif bit[n] == 0 and Si == '0':
                bit[n] = Ai 
                break
            Ai ^= bit[n]
    return 0

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    T = int(input())

    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()[:-1]
        print(xor_battle(N, A, S))

main()

Solution (Python):
T = int(input())

for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        base = A[j]
        for v in win:
            base = min(base, base ^ v)

        if S[j] == '0':
            win.add(base)
        else:
            if base:
                print('1')
                break
    else:
        print('0')

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(i) for i in input().split()]
    S = input()

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = a if a < a ^ b else a ^ b

        if a:
            if s == "1":
                ans = 1
                break
            B.append(a)

    print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

t = I()
for _ in range(t):
    n = I()
    a = LI()
    s = input()
    t = []
    for i, Ai in enumerate(a[::-1]):
        for Ti in t:
            if Ai ^ Ti < Ai: 
                Ai ^= Ti
        if Ai != 0 and s[n-i-1] == '0':
            t.append(Ai)
        elif Ai != 0 and s[n-i-1] == '1':
            print(1)
            break
    else:
        print(0)

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(i) for i in input().split()]
    S = input()

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = a if a < (b := a ^ b) else b

        if a:
            if s == "1":
                ans = 1
                break
            B.append(a)

    print(ans)

Solution (Python):
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    if S[-1] == '1':
        print(1)
        continue

    list0 = [0] * 64

    for a, s in zip(reversed(A), reversed(S)):
        blen = a.bit_length()
        for i in range(blen, 0, -1):
            if a.bit_length() < i: continue
            if list0[i - 1]:
                a ^= list0[i - 1]
                if a == 0: break

        else:
            if s == '1':
                ans = 1
                break
            else:
                list0[a.bit_length() - 1] = a

    else:
        ans = 0

    print(ans)

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().strip()

    ignore = []

    win = True

    for i in range(N - 1, -1 ,-1):
        startLen = len(ignore)
        
        curr = A[i]
        for v in ignore:
            if curr ^ v < curr:
                curr = curr ^ v
        if curr != 0:
            ignore.append(curr)
            ignore.sort(reverse = True)
        
        endLen = len(ignore)
        if S[i] == '1' and startLen != endLen:
            win = False
            break
            

    if win:
        print(0)
    else:
        print(1)

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(i) for i in input().split()]
    S = input()

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = min(a, a ^ b)

        if a:
            if s == "1":
                ans = 1
                break
            B.append(a)

    print(ans)

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(i) for i in input().split()]
    S = input()

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = min(a, a ^ b)

        if a:
            if s == "1":
                ans = 1
                break
            else:
                B.append(a)

    print(ans)

Solution (Python):
sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

T = ni()
for _ in range(T):
    N = ni()
    A = [ni() for _ in range(N)]
    S = ns()

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = min(a, a ^ b)

        if a:
            if s == "1":
                ans = 1
                break
            else:
                B.append(a)

    print(ans)

Solution (Python):
class VectorSpace01:
    def __init__(self):
        self.E = []
    
    def chk(self, n):
        for e in self.E:
            n = min(n, n ^ e)
        return 1 if n == 0 else 0
    
    def add(self, n):
        for e in self.E:
            n = min(n, n ^ e)
        if n: self.E.append(n)
        return 1 if n == 0 else 0
    
    def dimension(self):
        return len(self.E)

T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(a) for a in input().split()]
    S = [int(a) for a in input()]
    vs = VectorSpace01()
    for i in range(N)[::-1]:
        a = vs.add(A[i])
        if S[i] and a == 0:
            print(1)
            break
    else:
        print(0)

Solution (Python):
def main():
    t = int(input())
    for _ in range(t):
        nn, aa, s, r, mm = int(input()), list(map(int, input().split())), input(), 0, []
        for ii in range(nn-1, -1, -1):
            ai = aa[ii]
            mm += [[(ai >> jj) & 1 for jj in range(64)]]
            n, i, j = r+1, 0, 0
            while i < n and j < 64:
                if mm[i][j] == 1 and mm[n-1][j] == 0:
                    i += 1
                    j += 1
                    continue
                if mm[i][j] == 0:
                    if mm[n-1][j] != 0:
                        for l in range(j, 64):
                            mm[i][l] ^= mm[n-1][l]
                    else:
                        j += 1
                        continue
                M2 = mm[i]
                for k in range(i+1, n):
                    M3 = mm[k][j]
                    mm[k][j] = 0
                    for l in range(j+1, 64):
                        mm[k][l] ^= M3*M2[l]
                i += 1
                j += 1
    
            if s[ii] == "0":
                if i > r:
                    r += 1
                else:
                    mm.pop()
            else:
                mm.pop()
                if i > r:
                    print(1)
                    break
        else:
            print(0)


main()

Solution (Python):
def solve():
    dp = [0]
    for a, s in zip(A[::-1], S[::-1]):
        
        x = a
        for y in dp:
            
            x = min(x, x ^ y)
        
        if s == "0":
            if x:
                dp.append(x)
        else:
            if x:
                return 1
        
    return 0


t = int(input())
for i in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    
    print(solve())

Solution (Python):
from collections import Counter
import math
import sys
from bisect import bisect,bisect_left,bisect_right
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def mod(): return 10**9+7
 
for _ in range(INT()):
    n = INT()
    
    
    arr = LIST()
    s = input()
    check = []
    flag = 0
    for i in range(n-1,-1,-1):
        
        x = arr[i]
        for j in range(len(check)):
            x = min(x,x^check[j])

        if x == 0:
            continue
        if s[i] == '0':
            check.append(x)
        else:
            print(1)
            flag = 1
            break
    if flag == 0:
        print(0)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

t = int(readline())

def get_base(x,basis):
    for b in basis:
        x = min(x,x^b)
    return x

for _ in range(t):
    n = int(readline())
    a = list(map(int,readline().split()))
    s = readline().strip()

    basis = []
    for si,ai in zip(s[::-1], a[::-1]):
        x = get_base(ai,basis)
        if(si=='0')&(x>0):
            basis.append(x)
        elif(si=='1')&(x>0):
            print(1)
            break
    else:
        print(0)

Solution (Python):
def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    s = list(input())
    basis = []
    for i in range(n-1, -1, -1):
        for v in basis:
            if a[i] > (a[i] ^ v):
                a[i] = a[i] ^ v
        if a[i] > 0:
            if s[i] == '0':
                basis.append(a[i])
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    print(solve())

Solution (Python):

import sys


def main():

    def solve(S, A):
        X = []
        for s, v in zip(S[::-1], A[::-1]):
            for x in X:
                if v & (x & -x):
                    v ^= x
            if v:
                if s == "0":
                    X.append(v)
                else:
                    return 1
        return 0

    T = int(input())
    for t in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        print(solve(S, A))

    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():

    
    
    
    
    
    
    

    
    
    
    
    
    
    

    T = int(input())
    for t in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        lose = False

        
        
        X = []
        for i in reversed(range(N)):
            v = A[i]
            for x in X:
                if v & (x & -x):
                    v ^= x
            if v != 0:
                if S[i] == "0":
                    X.append(v)
                else:
                    lose = True
                    break
        if lose == True:
            print(1)
        else:
            print(0)

    return


if __name__ == '__main__':
    main()

Solution (Python):
I=input
n=int
for i in range(n(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    [i:=(i^k*(i^k<i))for k in t];j=n(j);t+=[i*(j^1)];x|=(i>0)&j
  print(x)

Solution (Python):
I=input
n=int
for i in range(n(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    j=n(j);t+=[i*(j^1)];x|=(i>0)&j
  print(x)

Solution (Python):
I=input
n=int
for i in range(n(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    j=n(j);t.append(i*(j^1));x|=(i>0)&j
  print(x)

Solution (Python):
I=input
n=int
for i in range(n(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    j=n(j);t.append(i*(j^1));x|=(i>0)&j
  print(x)

Solution (Python):
I=input
n=int
for i in range(n(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    j=n(j);t.append(i*(j^1));x|=(i>0)&j
  print(x)

Solution (Python):
T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    base = []
    for i in range(1,N+1):
        temp = A[-i]
        for x in base:
            temp = min(temp,temp^x)
        if temp != 0:
            if S[-i] == '1':
                print('1')
                break
            else:
                base.append(temp)
    else:
        print('0')

Solution (Python):
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    b=[]
    for i in range(n)[::-1]:
        for e in b:
            a[i]=min(a[i],a[i]^e)
        if a[i]:
            if s[i]=="0":
                b+=[a[i]]
            else:
                print(1)
                break
    else:
        print(0)

Solution (Python):

import numpy as np

def msb(x,ma=59):
    for i in range(ma,-1,-1):
        if (x>>i)&1:
            return i
    return len()
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    
    
    msbs=[0 for i in range(60)]
    for i in range(n-1,-1,-1):
        now=a[i]
        m=59
        
        while True:
            m=msb(now,m)
            if msbs[m]==0:
                f=True
                break
            now=msbs[m]^now
            if now==0:
                f=False
                break
        if s[i]=="0":
            if f:
                msbs[m]=now
        else:
            if f:
                print(1)
                break
    else:
        print(0)

Solution (Python):
T=int(input())
for t in range(T):
    N=int(input())
    A=list(map(int,input().split()))[::-1]
    S=input()
    S=[1 if c=='1' else 0 for c in S][::-1]
    l=[]
    r=0
    for i,a in enumerate(A):
        if S[i]:
            for e in sorted(l)[::-1]:
                b=pow(2,e.bit_length()-1)
                if a&b:
                    a^=e
            if a:
                r=1
        else:
            for e in l:
                if a>e^a:
                    a^=e
            if a:
                l.append(a)
    print(r)

Solution (Python):

class F2n:
    
    def __init__(self,LIST):
        self.basis = []
        for ele in LIST:
            for vec in self.basis:
                ele = min(ele, vec^ele)
            if ele:
                self.basis.append(ele)
    
    def Add(self, ele):
        for vec in self.basis:
            ele = min(ele, ele^vec)
        if ele:
            self.basis.append(ele)
            return True
        else:
            return False

def solve():
    n=int(input())
    a=list(map(int,input().split()))[::-1]
    s=input()[::-1]
    h=F2n([])
    for i in range(n):
        if h.Add(a[i]):
            if s[i]=="1":
                print(1)
                return
    print(0)
t=int(input())
for _ in range(t):
    solve()

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18

def ddprint(x):
  if DBG:
    print(x)

def cover0(c,d):
    m = len(c)
    for i in range(m):
        if c[i]==0:
            continue
        k = -1
        for j in range(62):
            b = 1<<j
            if c[i]&b != 0:
                k = j
                break
        for j in range(i+1,m):
            if c[j]&b != 0:
                c[j] ^= c[i]
        for j in range(len(d)):
            if d[j]&b != 0:
                d[j] ^= c[i]
    return sum(d)==0

t = inn()
for tt in range(t):
    n = inn()
    a = inl()
    s = ins()
    top = n
    to0 = []
    to1 = []
    done = False
    while top>0:
        prev0 = top
        while top>0 and s[top-1]=='0':
            top -= 1
        top0 = top
        to0.extend(a[top0:prev0])
        prev1 = top
        while top>0 and s[top-1]=='1':
            top -= 1
        top1 = top
        to1.extend(a[top1:prev1])
        cc = [x for x in to0]
        dd = [x for x in to1]
        if not cover0(cc,dd):
            print(1)
            done = True
            break
    if not done:
        print(0)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


t = I()
for _ in range(t):
    n = I()
    A = LI()
    s = S()
    basis = []
    for i in range(n - 1, -1, -1):
        v = A[i]
        for b in basis:
            v = min(v, v ^ b)
        if v:
            if s[i] == '1':
                print(1)
                break
            basis += [v]
    else:
        print(0)

Solution (Python):

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    basis=[]
    for i in range(n-1,-1,-1):
      	
        for e in basis:
            a[i]=min(a[i],a[i]^e)
        if a[i]:
            if s[i]=="0":
                basis.append(a[i])
            else:
                print(1)
                return
    print(0)

t=int(input())
for _ in range(t):
    solve()