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):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    M=60
    


    
    def pipo(x):
        cnt=0
        for i in range(M):
            if x==0:
                return cnt
            else:
                x=x//2
                cnt+=1
    

        
    
    for _ in range(T):
        N=I()
        A=LI()
        S=list(input())
        
        Vec=[]
        flag=1
        for i in range(N-1,-1,-1):
            
            if S[i]=="0":
                if Vec==[]:
                    Vec.append((A[i],pipo(A[i])))
                else:
                    now=A[i]
                    p=pipo(A[i])
                    for v in Vec:
                        if v[1]==p:
                            now=now^v[0]
                            p=pipo(now)
                    if now!=0:
                        Vec.append((now,pipo(now)))
                        Vec.sort(reverse=True)
                            
                
            else:
                
                now=A[i]
                for v in Vec:
                    if v[1]==pipo(now):
                        now=now^v[0]
                if now!=0:
                    flag=0

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

main()

Solution (Python):

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(item) for item in input().split()]
    s = input().rstrip()
    if s[-1] == "1":
        print(1)
        continue
    group = []
    prev = "-1"
    for ch, num in zip(s, a):
        if prev != ch:
            group.append([])
        group[-1].append(num)
        prev = ch
    group.reverse()
    tools = []
    ok = True
    for itr, g in enumerate(group):
        if itr % 2 == 0:
            for item in g:
                tools.append(item)
        else:
            tl = tools[:]
            index = 0
            for i in range(64, -1, -1):
                flag = 0
                for j in range(index, len(tl)):
                    if tl[j] & (1 << i):
                        flag = 1
                        tl[index], tl[j] = tl[j], tl[index]
                        break
                for j in range(index + 1, len(tl)):
                    if tl[j] & 1 << i:
                        tl[j] ^= tl[index]
                if flag == 1:
                    index += 1
            for item in g:
                current = 0
                for val in tl:
                    index = len(bin(val)) - 3
                    if item >> index != current >> index:
                        current ^= val
                if current != item:
                    ok = False
    if ok:
        print(0)
    else:
        print(1)

Solution (Python):
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    ans = '0'
    for i in range(N):
        if S[i]=='1':
            l = []
            for j in range(i+1,N):
                if S[j]=='0':
                    l.append(A[j])
            for k in range(len(l)):
                l.sort()
                for j in range(len(l)-1):
                    if l[j+1]^l[j] < l[j+1]:
                        l[j+1],l[j] = l[j],l[j+1]^l[j]
                
            s = A[i]
            for j in range(len(l)-1,-1,-1):
                if s^l[j] < s:
                    s ^= l[j]
            if s != 0:
                ans = '1'
    print(ans)
def main():
    T = int(input())
    for t in range(T):
        solve()

if __name__ == '__main__':
    main()

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

def matmul(a, b, mod):
    m = len(a)
    l = len(a[0])
    n = len(b[0])
    ret = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            e = 0
            for k in range(l):
                e = (e + a[i][k] * b[k][j]) % 2
            ret[i][j] = e
    return ret

def calc(X, v, r):
    rr = 0
    for i in range(r, D):
        if v[i][0] == 1:
            rr = i
            break
    v[rr], v[r] = v[r], v[rr]
    X[rr], X[r] = X[r], X[rr]
    for i in range(D):
        if i == r or v[i][0] == 0:
            continue
        for c in range(D):
            X[i][c] = (X[i][c] + X[r][c]) % 2

T = int(input())
D = 64
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    X = [[int(i == j) for j in range(D)] for i in range(D)]
    r = 0
    for i in range(N)[::-1]:
        v = [[A[i] >> j & 1] for j in range(D)]
        if S[i] == '0':
            v = matmul(X, v, 2)
            if any(v[j][0] == 1 for j in range(r, D)):
                calc(X, v, r)
                r += 1
        else:
            v = matmul(X, v, 2)
            if any(v[j][0] == 1 for j in range(r, D)):
                print(1)
                break
    else:
        print(0)

Solution (Python):
import sys
input = sys.stdin.readline
def judge(mat,x,pivot):
  b = x.bit_length()
  cnt = 0
  for i in range(b)[::-1]:
    if x&1<<i:
      if i not in pivot:
        return False
      for j in range(cnt,len(mat)):
        if mat[j]&1<<i:
          x ^= mat[j]
          cnt = j+1
          break
  if x == 0:
    return True
  else:
    return False
def add(mat,x,pivot):
  b = x.bit_length()
  cnt = 0
  for i in range(b)[::-1]:
    if x&1<<i:
      if i in pivot:
        for j in range(cnt,len(mat)):
          if mat[j]&1<<i:
            x ^= mat[j]
            cnt = j+1
            break
      else:
        pivot.add(i)
        for j in range(len(mat)):
          if mat[j] < x:
            mat.insert(j,x)
            for k in range(i)[::-1]:
              if mat[j]&1<<k and k in pivot:
                for l in range(j+1,len(mat)):
                  if mat[l]&1<<k:
                    mat[j] ^= mat[l]
            x = mat[j]
            break
        else:
          mat.append(x)
        for j in range(len(mat)):
          if mat[j] > x and mat[j]&1<<i:
            mat[j] ^= x
        break
t = int(input())
for _ in range(t):
  n = int(input())
  a = list(map(int,input().split()))
  s = input().rstrip()
  pivot = set()
  mat = []
  for i in range(n)[::-1]:

    x = a[i]
    if s[i] == "0":
      if judge(mat,x,pivot):
        continue
      else:
        add(mat,x,pivot)
    else:
      if judge(mat,x,pivot):
        continue
      else:
        print(1)
        break
  else:
    print(0)

Solution (Python):
def kosu(kitei, aaa, tuika):
    global now_ret
    ret = 0
    n=len(kitei)
    ret2=0
    kitei.append(aaa)
    n+=1
    for i in range(n):
        if kitei[i]:
            ret2 += 1
            x = 0
            while (2**(x+1)) <= kitei[i]:
                x += 1
            for y in range(i+1, n, 1):
                if kitei[y] & (2 ** x):
                    kitei[y] ^= kitei[i]
    
    if now_ret==ret2:
        return 1
    else:
        if tuika==1:
            now_ret+=1
        return 0
 
 
def solve(n, alist, s):
    kitei=[0]
    answer=0
    for i in range(n):
        teban=s[n-i-1]
        now=alist[n-i-1]
        if teban=='0':
            if kosu(kitei, now, 1)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now, 0)>0:
                pass
            else:
                answer=1
        
    return answer
 
t=int(input())
for i in range(t):
    now_ret=0
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()
    print(solve(n, alist, s))

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

for _ in range(T):
    N = int(input())
    As = list(map(int, input().split()))
    S = list(input())
    mine = [0] * 61
    for a, s in reversed(list(zip(As, S))):
        bl = a.bit_length()
        if s == '0':
            while bl > 0:
                if (a >> (bl-1)) & 1:
                    if mine[bl] == 0:
                        mine[bl] = a
                        break
                    a ^= mine[bl]
                bl -= 1

        else:
            while bl > 0:
                if (a >> (bl-1)) & 1:
                    if mine[bl] == 0:
                        print(1)
                        break
                    a ^= mine[bl]
                bl -= 1
            else:
                continue
            break
    else:
        print(0)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

def least_bit_set(x):
	return x & (-x)


def delete_zeros_from(values, start):
	i = start
	for j in range(start, len(values)):
		if values[j] != 0:
			values[i] = values[j]
			i += 1
	del values[i:]


def eliminate(values):
	values = list(values)
	i = 0
	while True:
		delete_zeros_from(values, i)
		if i >= len(values):
			return values
		j = i
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) < least_bit_set(values[j]):
				j = k
		values[i], values[j] = (values[j], values[i])
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) == least_bit_set(values[i]):
				values[k] ^= values[i]
		i += 1


def in_span(x, eliminated_values):
	for y in eliminated_values:
		if least_bit_set(y) & x != 0:
			x ^= y
	return x == 0









t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	values = []
	ok = True
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			values.append(a[i])
		else:
			elim = eliminate(values)
			if not in_span(a[i], elim):
				ok = False
				break
	if ok:
		print(0)
	else:
		print(1)

Solution (Python):
from itertools import groupby, chain
from operator import itemgetter


def sweep(l):
    result = []
    s = set(l)
    while s:
        a = max(s)
        b = 1 << (a.bit_length() - 1)
        s = {t ^ a if t >= b else t for t in s}
        s.discard(0)
        result.append([a, b])

    return result


t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    s = input()

    if s[-1] == '1':
        buf.append(1)
        continue

    grp = [list(map(itemgetter(1), itr)) for c, itr in groupby(zip(s, aaa), key=itemgetter(0))]
    if s[0] == '0':
        grp = grp[1:]
    grp1 = grp[0::2]
    grp0 = grp[1::2]
    erasable = [False] * sum(len(g) for g in grp1)
    for i in range(len(grp1)):
        l1 = list(chain(*grp1[:i + 1]))
        l0 = list(chain(*grp0[i:]))
        s0 = sweep(l0)

        for a, b in s0:
            for i in range(len(l1)):
                if l1[i] & b:
                    l1[i] ^= a

        for j, c in enumerate(l1):
            if c == 0:
                erasable[j] = True

    if all(erasable):
        buf.append(0)
    else:
        buf.append(1)


print('\n'.join(map(str, buf)))

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = list(map(int, input()))
    
    for i in range(N-1, -1, -1):
        ai = A[i]
        if ai==0:
            continue
        top = ai.bit_length() - 1
        assert ai & 1<<top
        for j in range(i-1, -1, -1):
            if A[j] >> top & 1:
                A[j] ^= ai
    for a, c in zip(A[::-1], S[::-1]):
        if c==1 and a:
            break
    else:
        print("0")
        continue
    print("1")

Solution (Python):
def collapse(A):
    R = []
    a = max(A)
    n = a.bit_length()
    B = [set() for _ in range(n)]
    for a in A:
        B[a.bit_length()].add(a)
    for i in reversed(range(n)):
        if not B[i]:
            continue
        b = B[i].pop()
        R.append(b)
        for k in B[i]:
            k ^= b
            B[k.bit_length()].add(k)
    return R

def solve(N, A, S):
    B = [0] * 64
    for a, s in zip(reversed(A), reversed(S)):
        if s == '1':
            n = a.bit_length() - 1
            while a != 0:
                if B[n] == 0:
                    return 1
                a ^= B[n]
                n = a.bit_length() - 1
        else:
            n = a.bit_length() - 1
            while a != 0 and B[n] != 0:
                a ^= B[n]
                n = a.bit_length() - 1
            if a == 0:
                continue
            B[n] = a
    return 0
    
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        print(solve(N, A, S))
main()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    for t in range(int(input())):
        N = int(input())
        A = list(map(int, input().split()))
        S = input().rstrip('\n')
        A.reverse()
        S = S[::-1]

        A0 = [0] * 60
        A1 = [0] * 60
        zero = 0
        one = 0
        for i, a in enumerate(A):
            if S[i] == "0":
                for j in range(60):
                    A0[j] ^= ((a >> j & 1) << zero)
                zero += 1
            else:
                for j in range(60):
                    A1[j] ^= ((a >> j & 1) << one)
                one += 1

        B = [0] * 60
        for i in range(60):
            B[i] = A0[i] + (A1[i] << zero)

        rnk = 0
        for i in range(zero):
            
            for j in range(rnk, 60):
                if B[j] >> i & 1:
                    B[j], B[rnk] = B[rnk], B[j]
                    b = B[rnk]
                    
                    for jj in range(60):
                        if jj == rnk:
                            continue
                        if B[jj] >> i & 1:
                            B[jj] ^= b
                    rnk += 1
                    break

        cnt0 = 0
        cnt1 = zero
        r = -1
        win = 0
        for s in S:
            if s == "0":
                if r+1 >= len(B):
                    break
                if B[r+1] >> cnt0 & 1:
                    r += 1
                cnt0 += 1
            else:
                rr = -1
                for j in range(60):
                    if B[j] >> cnt1 & 1:
                        rr = j
                if rr > r:
                    win = 1
                    break
                cnt1 += 1
        print(win)


if __name__ == '__main__':
    main()

Solution (Python):
import os

import sys
import numpy as np

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




DIGIT = (10 ** 18).bit_length()


def solve_f2(mat, last_col, rank):
    
    for col in range(last_col, mat.shape[1] - 1):
        if rank >= DIGIT:
            break
        last_col = col
        row = mat[rank:, col].argmax() + rank
        if not mat[row, col]:
            continue
        pivot = mat[row].copy()
        mat[mat[:, col]] ^= pivot
        mat[row] = mat[rank]
        mat[rank] = pivot
        rank += 1

    if rank < DIGIT and mat[rank:].any():
        
        return False, last_col, rank
    else:
        return True, last_col, rank


def solve(N, A, S):
    if S[-1] == '1':
        return 1

    
    S = (np.array(list(S), dtype=int) == 1)[::-1]
    A = np.array(A, dtype=int)[::-1]

    a_mat = []
    for d in reversed(range(DIGIT)):
        a_mat.append(A >> d & 1)
    mat = np.array(a_mat).astype(bool)

    rank = 0
    for col in range(N):
        if S[col]:
            
            if mat[rank:, col].any():
                
                return True
        if rank >= DIGIT:
            return False
        row = mat[rank:, col].argmax() + rank
        if not mat[row, col]:
            continue
        pivot = mat[row].copy()
        mat[mat[:, col]] ^= pivot
        mat[row] = mat[rank]
        mat[rank] = pivot
        rank += 1
    return False


T = int(sys.stdin.buffer.readline())
for _ in range(T):
    N = int(sys.stdin.buffer.readline())
    A = list(map(int, sys.stdin.buffer.readline().split()))
    S = sys.stdin.buffer.readline().decode().rstrip()
    ans = solve(N, A, S)
    print(int(ans))

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




def least_bit_set(x):
    return x & (-x)


def delete_zeros_from(values, start):
    i = start
    for j in range(start, len(values)):
        if values[j] != 0:
            values[i] = values[j]
            i += 1
    del values[i:]


def eliminate(values):
    values = list(values)
    i = 0
    while True:
        delete_zeros_from(values, i)
        if i >= len(values):
            return values
        j = i
        for k in range(i + 1, len(values)):
            if least_bit_set(values[k]) < least_bit_set(values[j]):
                j = k
        values[i], values[j] = (values[j], values[i])
        for k in range(i + 1, len(values)):
            if least_bit_set(values[k]) == least_bit_set(values[i]):
                values[k] ^= values[i]
        i += 1


def in_span(x, eliminated_values):
    for y in eliminated_values:
        if least_bit_set(y) & x != 0:
            x ^= y
    return x == 0


t = I()
for _ in range(t):
    n = I()
    A = LI()
    s = S()
    flg = 0
    values = []
    for j in range(n - 1, -1, -1):
        if int(s[j]) == 0:
            values += [A[j]]
            values = eliminate(values)
        else:
            if not in_span(A[j], values):
                print(1)
                break
    else:
        print(0)

Solution (Python):
import bisect
from itertools import accumulate

T = int(input())

for _ in range(T):
    N = int(input())
    As = list(map(int, input().split()))
    S = input()
    possible_xor = []
    if S[-1] == '1':
        print(1)
        continue
    flg = True
    for c, A in reversed(list(zip(S, As))):
        if c == '0':
            for xor in possible_xor[::-1]:
                if A.bit_length() == xor.bit_length():
                    A ^= xor
                elif A > xor:
                    break
            possible_xor.insert(bisect.bisect_left(possible_xor, A), A)
        else:
            for xor in possible_xor[::-1]:
                if A.bit_length() == xor.bit_length():
                    A ^= xor
            if A != 0:
                flg = False
                break
    if flg:
        print(0)
    else:
        print(1)

Solution (Python):
def base(a, f=False):
    k = 0
    for i in range(64):
        for ind in range(k, len(a)):
            j = a[ind]
            if (j >> i) & 1 == 1:
                break
        else:
            continue

        a[ind], a[k] = a[k], a[ind]
        for ind, j in enumerate(a):
            if ind == k:
                continue
            if (j >> i) & 1 == 1:
                a[ind] ^= a[k]
        k += 1
        if k >= len(a):
            break
    return a[:k]


t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(i) for i in input().split()]
    s = input()

    b = []
    for i in reversed(range(n)):
        if s[i] == '0':
            b = base(b + [a[i]])

        else:
            c = base(b[:] + [a[i]])
            if len(c) != len(b):
                print(1)
                break

    else:
        print(0)

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

T=int(input())

def base(B):

    L=len(B)
    flag=1
    
    while flag:
        B.sort(reverse=True)
        
        flag=0

        for i in range(L):
            for j in range(i+1,L):
                if B[i]^B[j]<B[i]:
                    B[i]=B[i]^B[j]
                    flag=1
                    break
            if flag:
                break
    return B     

def rep(x):
    flag=1

    while flag:
        flag=0
        for b in B:
            if b^x<x:
                x=b^x
                flag=1
                break
    return x

for tests in range(T):
    N=int(input())
    A=list(map(int,input().split()))
    B=[]
    S=input().strip()

    flag=1

    for i in range(N-1,-1,-1):
        if flag==0:
            break
        if S[i]=="0":
            v=rep(A[i])

            if v==0:
                continue
            B.append(v)
            B=base(B)

        else:
            if rep(A[i])!=0:
                print(1)
                flag=0
                break

    if flag:
        print(0)

Solution (Python):
import sys
readline = sys.stdin.readline
T = int(readline())
Ans = [None]*T
for qu in range(T):
    N = int(readline())
    A = list(map(int, readline().split()))
    S = list(map(int, readline().strip()))
    
    if len(set(A)) == 1:
        Ans[qu] = S[-1]
        continue
    
    if S[-1] == 1:
        Ans[qu] = 1
        continue
    
    stack = [0]*61
    for i in range(N-1, -1, -1):
        a = A[i]
        for j in range(60, -1, -1):
            if a&(1<<j):
                a ^= stack[j]
        
        if S[i] == 0:
            if a:
                stack[a.bit_length()-1] = a
            else:
                continue
        else:
            if a:
                Ans[qu] = 1
                break
    else:
        Ans[qu] = 0

print('\n'.join(map(str, Ans)))

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    INT_BITS = 64
    n = ni()
    a = nl()[::-1]
    s = ns()[::-1]
    lis = [0]*64
    for i in range(n):
        if s[i] == '1':
            c = a[i]
            for x in lis[::-1]:
                if x == 0:
                    continue
                if c & (1 << (x.bit_length() - 1)):
                    c ^= x
            if c:
                print(1)
                return
        else:
            c = a[i]
            for x in lis[::-1]:
                if x == 0:
                    continue
                if c & (1 << (x.bit_length() - 1)):
                    c ^= x
            if c:
                lis[c.bit_length() - 1] = c
    print(0)
    return

T = ni()
for _ in range(T):
    solve()

Solution (Python):
from heapq import heappush, heappop


def calcSpace():
    H = []
    hpush = lambda x: heappush(H, -x)
    hpop = lambda: -heappop(H)
    for x in X:
        hpush(x)
    
    E = [0] * 60
    while H:
        x = hpop()
        b = x.bit_length() - 1
        if E[b]:
            x ^= E[b]
            if x: hpush(x)
        else:
            E[b] = x
    
    return E
    
def chk(y):
    y0 = y
    for i in range(60)[::-1]:
        if y >> i & 1:
            if V[i]:
                y ^= V[i]
                
                if y == 0: return 1
            else:
                return 0

def chk_all():
    for y in Y:
        if chk(y) == 0:
            return 1
            break
    else:
        return 0
    
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()]
    
    if 0:
        print("N =", N)
        print("A =", A)
        print("S =", S)
    
    X = []
    Y = []
    i = N - 1
    ans = 0
    while i >= 0:
        while i >= 0:
            if S[i]: break
            X.append(A[i])
            i -= 1
        while i >= 0:
            if S[i] == 0: break
            Y.append(A[i])
            i -= 1

            V = calcSpace()
            
            
            
            if chk_all():
                ans = 1
                i = -1
    print(ans)

Solution (Python):
import sys
from numba import njit
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8,)', cache=True)
def keta(x):
    ret = -1
    while x >= 1:
        x >>= 1
        ret += 1
    return ret

@njit('(i8,i8[::1],i4[::1])', cache=True)
def solve(N, A, S):
    if np.all(S == 0):
        return True
    if S[-1] == 1:
        if A[-1] == 0:
            return solve(N - 1, A[:-1], S[:-1])
        else:
            return False
    
    i = np.where(S == 1)[0].max() + 1
    A1 = A[:i]
    B = A[i:]
    while True:
        B = B[B != 0]
        if len(B) == 0:
            break
        x = B.max()
        k = keta(x)
        A1 ^= ((A1 >> k) & 1) * x
        B ^= ((B >> k) & 1) * x
    N = len(A1)
    return solve(N, A1, S[:N])

def main():
    T = int(readline())
    for _ in range(T):
        N = int(readline())
        A = np.array(readline().split(), np.int64)
        S = np.array(list(readline().decode().rstrip()), np.int32)
        x = 0 if solve(N, A, S) else 1
        print(x)

main()

Solution (Python):
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = list(map(int, input()))
    
    for i in range(N-1, -1, -1):
        ai = A[i]
        if ai==0:
            continue
        top = ai.bit_length() - 1
        assert ai & 1<<top
        for j in range(i-1, -1, -1):
            if A[j] >> top & 1:
                A[j] ^= ai
    for a, c in zip(A[::-1], S[::-1]):
        if c==1 and a:
            break
    else:
        print("0")
        continue
    print("1")

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline




def solve():
    def normalize(v,basis):
        for b in basis:
            if v > v^b: v ^= b
        return v
    
    n, = map(int,readline().split())
    *a, = map(int,readline().split())
    s = input()
    
    basis = []
    b0 = []

    for e,si in zip(a[::-1],s[::-1]):
        if si=="0":
        	for b in basis:
        	    if e > e^b: e ^= b
        	if e: basis.append(e)

        if si=="1":
            v = normalize(e,basis)
            if v!=0:
                print(1)
                return

    
    print(0)
    return
        
        


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