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):
from collections import defaultdict
itl = lambda: list(map(int, input().strip().split()))


def solve():
    N = int(input())
    nums = itl()
    S = input().strip()

    basis = []
    for i in range(N - 1, -1, -1):
        v = nums[i]
        for b in basis:
            v = min(v, v ^ b)
        if v:
            if S[i] == '1':
                return 1
            basis.append(v)
    return 0    


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

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    check = True
    l = [0]*61
    for i in range(n-1,-1,-1):
        x = a[i]
        for j in range(60,-1,-1):
            if x & (1<<j):
                x ^= l[j]

        if s[i] == "0":
            if x:
                l[x.bit_length()-1] = x
        else:
            if x:
                print(1)
                check = False
                break
    if check:
        print(0)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    check = True
    l = [0]*61
    for i in range(n-1,-1,-1):
        x = a[i]
        for j in range(60,-1,-1):
            if x & (1<<j):
                x ^= l[j]

        if s[i] == "0":
            if x:
                l[x.bit_length()-1] = x
        else:
            if x:
                print(1)
                check = False
                break
    if check:
        print(0)

Solution (Python):
def solve(N, A, S):
    
    
    
    
    if int(S[-1]) == 1:
        return 1
    
    B = [None] * max(A).bit_length()
    for i in reversed(range(N)):
        a = A[i]
        s = int(S[i])
        
        if s == 0: 
            while a:
                l = a.bit_length()-1
                if B[l] == None:
                    B[l] = a
                    break
                a ^= B[l]
        else: 
            while a:
                l = a.bit_length()-1
                if B[l] == None:
                    return 1
                a ^= B[l]
    return 0

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

Solution (Python):
I=input
n=int
for i in range(int(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):


import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, sys.stdin.readline().rstrip().split())

X = 60 
def f(a, s, n):
    if s[-1] == "1":
        return 1

    y = bin(reduce(or_, a)).count("1")
    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    y -= 1
                    if y == 0:
                        return 0
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):
for i in range(int(input())):
  input()
  t=[]
  for i,j in zip(map(int,input().split()[::-1]),input()[::-1]):
    for k in t:i^=k*(i^k<i)
    if i and j=="0":t.append(i)
    if i and j=="1":print(1);break
  else:print(0)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def f(a, s, n):
    if s[-1] == "1":
        return 1

    X = max(a).bit_length()
    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    X -= 1
                    if X == 0:
                        return 0
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

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

def f(a, s, n):
    if s[-1] == "1":
        return 1

    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):
def solve():
    dp = [[] for _ in range(n+1)]
    dp[n].append(0)
    for i in range(n)[::-1]:
        dp[i] = dp[i+1]
        x = a[i]
        for y in dp[i+1]:
            x = min(x,x^y)
        if s[i] == "0":
            if x:
                dp[i].append(x)
        else:
            if x:
                return 1
    return 0
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    print(solve())

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


Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    Query.append((N, A, S))



def solve(N, A, S):
    Base = []
    for i in reversed(range(N)):
        s = S[i]
        a = A[i]
        if s == "0":
            for b in Base:
                a = min(a, a^b)
            if a:
                Base.append(a)
        else:
            for b in Base:
                a = min(a, a^b)
            if a:
                return False
                
    return True

for N, A, S in Query:
    print(0 if solve(N, A, S) else 1)

Solution (Python):
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            id = x.bit_length() - 1
            if id >= 0:
                s[id] = x

        res = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                update(A[i])
        print(res)


main()

Solution (Python):
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            id = x.bit_length() - 1
            if id >= 0:
                s[id] = x

        res = 0
        L2 = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                L2 = max(L2, A[i].bit_length())
                update(A[i])
        print(res)
main()

Solution (Python):
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L
        ID = A.index(max(A))

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            flag = False
            if x.bit_length() == 60:
                flag = True
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            id = x.bit_length() - 1
            if id >= 0:
                s[id] = x

        res = 0
        L2 = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                L2 = max(L2, A[i].bit_length())
                update(A[i])
        print(res)



main()

Solution (Python):
import sys
from copy import deepcopy

def canMake(k, Nums):
    L = len(Nums)
    index = 0
    bit = dict()
    for i in reversed(range(60)): 
        flag = 0
        tp = (1 << i)
        for j in range(index, L):
            if Nums[j] & tp == tp:
                flag = 1
                Nums[index], Nums[j] = Nums[j], Nums[index]
                bit[i] = index
                break
        if flag == 1:
            for j in range(L):
                if Nums[j] & tp == tp and index != j: Nums[j] ^= Nums[index]
        if flag == 1: index += 1

    
    ans = 0
    for i in range(60):
        if k & (1 << i) == (1 << i):
            if i in bit: ans ^= Nums[bit[i]]
    if ans == k: return True
    else: return False


def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = []
        for i in reversed(range(N)):
            if S[i] == "0":
                used.append(A[i])
            else:
                compare = deepcopy(used)
                if not canMake(A[i], compare):
                    Ans[t] = 1
                    break
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from copy import deepcopy

def canMake(k, Nums):
    L = len(Nums)
    index = 0
    bit = []
    for i in reversed(range(60)):
        flag = 0
        for j in range(index, L):
            if Nums[j] & (1 << i) == (1 << i):
                flag = 1
                Nums[index], Nums[j] = Nums[j], Nums[index]
                bit.append(i)
                break
        if flag == 1:
            for j in range(L):
                if Nums[j] & (1 << i) == (1 << i) and index != j: Nums[j] ^= Nums[index]
        if flag == 1: index += 1
    ans = 0
    for i in range(60):
        if k & (1 << i) == (1 << i):
            if i in bit: ans ^= Nums[bit.index(i)]
    if ans == k: return True
    else: return False


def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = []
        for i in reversed(range(N)):
            if S[i] == "0":
                used.append(A[i])
            else:
                compare = deepcopy(used)
                if not canMake(A[i], compare):
                    Ans[t] = 1
                    break
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





def kitei(SET,b):
  for k in SET:
    if k^b < b:
      b = k^b
  return {b}

def can_made_by(SET,b):
  if SET == set():
    return False
  for k in SET:
    if k^b < b:
      b = k^b
  if b:
    return False
  else:
    return True


def solve():
  N = I()
  A = IL()
  S_ = S()
  
  dp = [None for i in range(N+1)]
  dp[N] = {0}
  for i in range(N)[::-1]:
    if S_[i] == "0":
      if dp[i+1]:
        dp[i] = dp[i+1] | kitei(dp[i+1],A[i])
      else:
        dp[i] = dp[i+1]
    else:
      if can_made_by(dp[i+1],A[i]):
        dp[i] = dp[i+1]
      else:
        dp[i] = set()
  if dp[0] == set():
    print(1)
  else:
    print(0)
  
T = I()
for _ in range(T):
  solve()

Solution (Python):
def main():
    def sweep(arr):
        col = max(arr).bit_length()
        row = len(arr)

        rank = 0
        for c in range(col-1, -1, -1):
            piv = -1
            for r in range(rank, row):
                if arr[r] >> c & 1:
                    piv = r
            if piv == -1:
                continue

            arr[piv], arr[rank] = arr[rank], arr[piv]

            for r in range(row):
                if r == rank:
                    continue
                if arr[r] >> c & 1:
                    arr[r] ^= arr[rank]

            rank += 1

        return sorted(arr[:rank], reverse=True)

    def solve():
        N = int(input())
        A = list(map(int, input().split()))[::-1]
        S = input()[::-1]
        B0 = []

        for a, s in zip(A, S):
            if s == '1':
                for b0 in B0:
                    if a >> b0.bit_length()-1 & 1:
                        a ^= b0
                if a:
                    return 1
            else:
                B0 = sweep(B0+[a])

        return 0

    for _ in [0]*int(input()):
        print(solve())


if __name__ == '__main__':
    main()

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

def check_base(bases, A):
	for n, b in bases:
		if A & (1 << n) != 0:
			A ^= b
	if A == 0:
		return None
	n = 0
	d = 1
	while True:
		if A & d != 0:
			return n, A
		n += 1
		d <<= 1

def append_base(bases, A):
	pair = check_base(bases, A)
	if pair != None:
		bases.append(pair)

def check(N, A_list, S):
	bases = []
	for i in range(N - 1, -1, -1):
		A = A_list[i]
		if S[i] == "0":
			append_base(bases, A)
		else:
			if check_base(bases, A):
				return False
	return True

for i in range(T):
	N = int(input())
	A_list = list(map(int, input().split()))
	S = input().strip()
	
	if check(N, A_list, S):
		print("0")
	else:
		print("1")

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

def standard_form(A):
    C = A[:]
    L = 60
    E = []
    ids = []
    for i in range(L):
        e = j0 = None
        mask = (1 << i)-1
        for j, a in enumerate(C):
            if (a >> i) & 1 and (a & mask) == 0:
                e = a
                j0 = j
                break
        else:
            continue
        ids.append(j0)
        for j, a in enumerate(C):
            if j0 == j:
                continue
            if (a >> i) & 1:
                C[j] ^= e
    return [C[e] for e in ids]


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

    task = set([0])

    now = s[n-1]
    if now == "1":
        print(1)
        continue


    q = []
    win = "0"
    for i in range(n-1, -1, -1):
        if now == "0":
            if s[i] == "0":
                q.append(a[i])
            else:
                q = standard_form(q)
                task = task | set(q)
                task = set(standard_form(list(task)))
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(q)
                q = set(q) | task
                q = set(standard_form(list(q)))
                if task != task | q:
                    win = "1"
                    break

                q = [a[i]]
                now = "0"

    if now == "1":
        q = standard_form(list(q))
        q = set(q) | task
        q = standard_form(list(q))
        q = set(q)
        if task != task | q:
            win = "1"

    print(win)

Solution (Python):



def solve(*args: str) -> str:
    t = int(args[0])
    ret = []
    for i in range(1, 3*t+1, 3):
        n = int(args[i])
        A = tuple(map(int, args[i+1].split()))
        S = tuple(map(int, tuple(args[i+2])))

        ans = False
        dp = [0]*(max(A).bit_length()+1)
        for a, s in reversed(tuple(zip(A, S))):
            m = a.bit_length()
            if s == 0:
                while 0 < a and 0 < dp[m]:
                    a ^= dp[m]
                    m = a.bit_length()
                if 0 < a:
                    dp[m] = a
            elif s == 1:
                while 0 < a:
                    if 0 < dp[m]:
                        a ^= dp[m]
                        m = a.bit_length()
                    else:
                        ans = True
                        break

        ret.append(1*ans)

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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

Solution (Python):
M = 60
def topbit(n):
    res = -1
    for i in range(M,-1,-1):
        if n&2**i!=0:
            res = i
            break
    return res

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    base = {}
    ans = '0'
    for i in range(N-1,-1,-1):
        if S[i]=='0':
            s = A[i]
            while s != 0:
                n = topbit(s)
                if n not in base:
                    base[n] = s
                    break
                else:
                    s ^= base[n]
        else:
            s = A[i]
            while s != 0:
                n = topbit(s)
                if n not in base:
                    ans = '1'
                    break
                else:
                    s ^= base[n]
    print(ans)

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

Solution (Python):
from bisect import insort

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

    is_ok = 0

    can = []
    for i in range(n - 1, -1, -1):
        a = aaa[i]
        if s[i] == '0':
            for (b, c) in can[::-1]:
                if a & b:
                    a ^= c
            if a:
                b = 1 << (a.bit_length() - 1)
                insort(can, (b, a))
        else:
            for (b, c) in can[::-1]:
                if a & b:
                    a ^= c
            if a:
                is_ok = 1
                break

    buf.append(is_ok)

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

Solution (Python):
import numpy as np
import math
import collections

T = int(input())
for i in range(T):
    x = 0
    L0 = [0]
    ans = 0
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    for i, s in enumerate(reversed(S)):
        tmp = A[N - 1 - i]
        for l0 in L0:
            if tmp ^ l0 < tmp:
                tmp = tmp ^ l0
        if tmp > 0:
            if s == "1":
                ans = 1
                break
            L0.append(tmp)
    print(ans)

Solution (Python):
def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])
 
    rank = 0
    for col in range(cnt_col):
        
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                pivot = row
                break
 
        
        if pivot == -1:
            continue
 
        
        A[pivot], A[rank] = A[rank], A[pivot]
 
        
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        rank += 1
 
    return A


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

    hand = [0]
    flag = False

    for i in range(n)[::-1]:
        val = a[i]
        if s[i] == "1":
            
            hand.sort(reverse=True)
            for num in hand:
                if val.bit_length() == num.bit_length():
                    val ^= num
            if val != 0:
                flag = True
        else:
            
            hand.append(val)
            
            hand = xor_gauss_jordan(hand)


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

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

                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):
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	basis = []
	ans = 0
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			for b in basis:
				a[i] = min(a[i], a[i]^b)
			if a[i]:
				basis.append(a[i])
		else:
			for b in basis:
				a[i] = min(a[i], a[i]^b)
			if a[i]:
				ans = 1
				break
	print(ans)

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

        
        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):
class VectorSpace:
    def __init__(self, k):
        self.k = k
        self.E = [0] * k
    
    def chk(self, n):
        for i in range(self.k)[::-1]:
            n = min(n, n ^ self.E[i])
        return 1 if n == 0 else 0
    
    def add(self, n):
        for i in range(self.k)[::-1]:
            n = min(n, n ^ self.E[i])
        if n: self.E[n.bit_length() - 1] = 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 = VectorSpace(60)
    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):
class VectorSpace:
    def __init__(self, k):
        self.k = k
        self.E = [0] * k
    
    def chk(self, n):
        for i in range(self.k)[::-1]:
            n = min(n, n ^ self.E[i])
        return 1 if n == 0 else 0
    
    def add(self, n):
        for i in range(self.k)[::-1]:
            n = min(n, n ^ self.E[i])
        if n: self.E[n.bit_length() - 1] = 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 = VectorSpace(60)
    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 solve(n, a_list, s):

    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            if a_list[i] == 0:
                continue
            r = 2 ** (a_list[i].bit_length() - 1)
            for j in range(i):
                if a_list[j] & r > 0:
                    a_list[j] = a_list[i] ^ a_list[j]
        else:
            if a_list[i] > 0:
                return 1
    return 0


def main():
    t = int(input())
    res_list = []
    for _ in range(t):
        n = int(input())
        a_list = list(map(int, input().split()))
        s = input()
        res = solve(n, a_list, s)
        res_list.append(res)
    for res in res_list:
        print(res)


def test():
    assert solve(2, [1, 2], "10") == 1
    assert solve(2, [1, 1], "10") == 0
    assert solve(6, [2, 3, 4, 5, 6, 7], "111000") == 0


if __name__ == "__main__":
    test()
    main()

Solution (Python):
def solve(N, A, S):
    B = [0] * 64
    for a, s in zip(reversed(A), reversed(S)):
        if s == '1':
            while a:
                n = a.bit_length() - 1
                if B[n] == 0:
                    return 1
                a ^= B[n]
        else:
            while a:
                n = a.bit_length() - 1
                if B[n] == 0:
                    B[n] = a
                    break
                a ^= B[n]
    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()