Xor Basis

/// prac prob : 
https://atcoder.jp/contests/abc141/tasks/abc141_f
https://atcoder.jp/contests/agc045/tasks/agc045_a
https://atcoder.jp/contests/abc236/tasks/abc236_f


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
#define   MP             make_pair
#define   pb             push_back
#define   EB             emplace_back
#define   nn             '\n'
#define   endl           '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   all(vec)       vec.begin(),vec.end()
#define   int            long long
#define   pii            pair<int,int>
#define   pdd            pair<double,double>
#define   ff             first
#define   ss             second
#define   yes            cout<<"YES\n"
#define   no             cout<<"NO\n"

using namespace std ;

typedef long long LL ;

const int MOD=998244353,Base=998244353 ;
const int N=1e6+7 ;
const int oo=1LL*1000*1000*1000*1000*1000*1000+7LL ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;

using i64 = long long;

int a[N] , n ;

/// basis for max query ... 

struct Basis {
    i64 a[64];
    bool insert(i64 x) {
        for (int i = 60; ~i; i--)
            if (x >> i & 1)
                if (a[i]) x ^= a[i];
                else return a[i] = x, true;
        return false;
    }
    i64 ask() {
        i64 res = 0;
        for (int i = 60; ~i; i--)
            res = max(res, res ^ a[i]);
        return res;
    }
    void init() {
        memset(a, 0, sizeof a);
    }
} b;

int32_t main()
{
    IOS

    cin>>n ;
    int x = 0 ;
    for(int i=1;i<=n;i++){
        cin>>a[i] ; x^=a[i] ;
        b.insert(a[i]) ;
    }

    cout<<b.ask()<<endl ;

    return 0 ;
}

/// check whether we can reduce or not ... 


struct Basis
{
    vector<int> basis;
    int reduce(int x)
    {
        for (auto b : basis) if ((x ^ b) < x) x ^= b;
        return x;
    }
    void insert(int x)
    {
        int r = reduce(x);
        if (r) basis.pb(r);
    }
};

int32_t main()
{
    IOS

    int test ;
    cin>>test ;
    while(test--)
    {
        cin>>n ;
        Basis b ;
        for(int i=0; i<n; i++)
        {
            cin>>a[i] ;
        }
        string s ;
        cin>>s ; bool f = 0 ;
        for(int i=n-1; i>=0; i--)
        {
            if(s[i]=='0')
                b.insert(a[i]) ;
            else if(b.reduce(a[i]))
                f=1 ;
        }
        cout<<f<<endl ;
    }

    return 0 ;
}