Problem Link : http://lightoj.com:81/volume/problem/1269

Solution Idea:

This solution idea is from Manuel Pineda (https://github.com/pin3da) .

/*

Supose that you have an array p, where p[i] is the "accumulative xor" up to i (i.e a[0] ^ a[1] ^ ... a[i]).

For all possible a[i], we can check all the previous a[j], (j < i) in the array "p" and compute the maximum and minimum value of a[i] ^ a[j].

  p.push_back(0);
  for (int i = 0; i < n; ++i) {
    cin >> t;
    cur ^= t;
    for (int j = 0; j < p.size(); ++j) {
      mmin = min(mmin, p[j] ^ cur);
      mmax = max(mmax, p[j] ^ cur);
    }
    p.push_back(cur);
  }
See the brute force solution for details.

This approach lead us to solve the problem, but is not fast enough.

In order to make the solution faster, we need to introduce a trie.

In this trie, we will to save all the prefixes using them binary representation. Use the standard algorithm for that.

If we look the previous solution, this is the equivalent to insert 'mask' in the array 'p'.

  void add(int mask) {
    int cur = 0;
    for (int i = 31; i >= 0; --i) {
      int next = (mask >> i) & 1;
      if (t[cur][next] == -1) {
        t[cur][next] = nodes;
        nodes++;
      }
      cur = t[cur][next];
    }
  }
Then we need to think about how to search the minimum (and the maximum) value that we could get if we perform the xor operation between a mask and all values in the tree. For this, we can make a kind of tree traversal.

The key idea here is : If I'm checking the ith bit of mask and I need the minimum possible value, I will try to advance in the tree using the edge which is equals to the ith bit of the mask in order to get 0 in the result (because we are looking for mask ^ some_number_in_the_tree).

If there is no such edge, I will advance using the other egde.

These words could be confusing, but the code is simpler.

  int get_min(int mask) {
    int cur = 0, ans = 0;
    for (int i = 31; i >= 0; --i) {
      int next = (mask >> i) & 1;
      if (t[cur][next] != -1) {
        ans <<= 1;
        cur = t[cur][next];
      } else {
        cur = t[cur][next ^ 1];
        ans <<= 1;
        ans++;
      }
    }
    return ans;
  }

*/

#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1LL<<50)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(ll N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct node
{
    bool stop;
    node *next[2];
    node()
    {
        stop=0;
        for(int i=0; i<2; i++)
            next[i]=NULL;
    }

};

ll power[50];

void insert(ll mask, node *cur)
{
    for(int i=31; i>=0; i--)
    {
        int id=check(mask,i);
        if(cur->next[id]==NULL)
            cur->next[id]=new node();
        cur=cur->next[id];
    }
    cur->stop=1;
}

ll query_max(ll mask, node *cur)
{
    ll ret=0;
    for(int i=31;i>=0;i--)
    {
        int id=check(mask,i);
        if(cur->next[id^1])
        {
            ret+=power[i];
            cur=cur->next[id^1];
        }
        else
            cur=cur->next[id];
    }
    return ret;
}

ll query_min(ll mask, node *cur)
{
    ll ret=0;
    for(int i=31;i>=0;i--)
    {
        int id=check(mask,i);
        if(cur->next[id])
        {
            cur=cur->next[id];
        }
        else
        {
            ret+=power[i];
            cur=cur->next[id^1];
        }
    }
    return ret;
}

void del(node *cur)
{
    for(int i=0;i<2;i++)
        if(cur->next[i])
            del(cur->next[i]);
    delete (cur);
}

//inline string to_str(ll n)
//{
//    bitset<32>bit(n);
//    return bit.to_string();
//}


int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

//    int aa;
//    cin>>aa;

//    cout<<to_str(aa)<<endl;


  power[0]=1;
  for(int i=1;i<=33;i++)
        power[i]=power[i-1]*2;


  node *root;
//   *small;

   int t;
   sf(t);
   TEST_CASE(t)
   {
       int n;
       sf(n);

       ll maxi=-infinity;
       ll mini=infinity;

       root=new node();
//       small=new node();

//        insert(to_str(0),root);
//        insert(to_str(0),small);
        insert(0,root);
        ll a;

       ll xx=0;

       for(int i=0;i<n;i++)
       {
            sfl(a);
            xx^=a;
//            string str=to_str(xx);
            maxi=max(maxi,query_max(xx,root));
            mini=min(mini,query_min(xx,root));
            insert(xx,root);
       }

    PRINT_CASE;

    pf("%lld %lld\n",maxi,mini);

    del(root);

   }
    return 0;
}