template<typename T>
class LinerBasis
{
public:
  LinerBasis(vector<T> &arr, T n): arr(arr), n(n)
  {
    basis.assign(BIT+1, 0);
    zero = false;
    compute();
  }
  void compute()
  {
    zero = false;
    for (int i = 1; i<=n; i++)
    {
      if (!insert(arr[i]))
      {
        zero = true;
      }
    }
  }

  bool insert(T num)
  {
    for (T i = BIT; i>=0; i--)
    {
      if ((num>>i)&1ll)
      {
        if (basis[i]==0)
        {
          basis[i] = num;
          return true;
        }
        num^=basis[i];
      }
    }
    return false;
  }

  bool haszero()
  {
    return zero;
  }

  vector<T> result()
  {
    return basis;
  }

private:  
  const int BIT = 60;
  vector<T> basis;
  vector<T> &arr;
  bool zero;
  T n;
};

template<typename T>
class LinerBasis
{
public:
  LinerBasis(vector<T> &arr, T n): basis(arr), n(n), len(0)
  {
    zero = false;
    compute();
  }
  void compute()
  {
    len = 1;
    for (int i = BIT; i>=0; i--)
    {
      for (int j = len; j<=n; j++)
      {
        if (basis[j]&(1ll<<i))
        {
          swap(basis[j], basis[len]);
          break;
        }
      }
      if (basis[len]&(1ll<<i))
      {
        for (int j = 1; j<=n; j++)
        {
          if (j!=len&&(basis[j]&(1ll<<i)))
          {
            basis[j] ^= basis[len];
          }
        }
        len++;
      }
    }
    len--;
    zero = (n!=len);
  }

  bool haszero()
  {
    return zero;
  }

  vector<T> result()
  {
    return basis;
  }

  T queryk(T k)
  {
    if (zero&&k==1) return 0;
    if (zero) k--;
    if (k>=(1ll<<len)) return -1;
    T ans = 0;
    for (int i = len, j = 0; i>=1; i--, j++)
    {
      ans^=basis[i];
    }
    return ans;
  }
  

private:  
  const int BIT = 60;
  vector<T> &basis;
  bool zero;
  T len;
  T n;
};