<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

275. To xor or not to xor
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The sequence of non-negative integers A1, A2, ..., AN is given. You are to find some subsequence Ai1, Ai2, ..., Aik (1 <= i1 < i2 < ... < ik <= N) such, that Ai1 XOR Ai2 XOR ... XOR Aik has a maximum value.

Input
The first line of the input file contains the integer number N (1 <= N <= 100). The second line contains the sequence A1, A2, ..., AN (0 <= Ai <= 10^18).

Output
Write to the output file a single integer number -- the maximum possible value of Ai1 XOR Ai2 XOR ... XOR Aik.

Sample test(s)

Input
3
11 9 5

Output
14
Author:	Michael R. Mirzayanov
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
## 1. Abridged Problem Statement

Given N non-negative integers A_1...A_n (1 <= N <= 100, 0 <= A_i <= 10^18), choose any subsequence (i.e. any subset) of them so that the bitwise XOR of its elements is as large as possible. Output that maximum XOR value.

## 2. Key Observations

- Bitwise XOR over {0,1}^61 forms a vector space over GF(2).
- Any subset XOR is a linear combination (over GF(2)) of the input bit-vectors.
- If we extract a basis of these vectors (so that each basis vector has a unique highest set bit), then any achievable XOR is a XOR-combination of a subset of basis vectors.
- To maximize the resulting number, we can greedily try to set high bits first by iterating through basis vectors in descending order of their highest bit.

## 3. Full Solution Approach

Step A: Build a XOR-basis
  - Maintain an array `basis[0...60]`, where `basis[k]` holds a basis vector whose highest set bit is k, or 0 if none.
  - To insert a new number x:
    - For bit k from 60 down to 0:
      - If x's k-th bit is 0, skip.
      - Else if `basis[k]` is 0, store `basis[k] = x` and stop.
      - Else replace x <- x XOR basis[k] and continue.
    - If x becomes 0, it is linearly dependent on the existing basis and is discarded.

Step B: Compute the maximum subset XOR
  - Initialize `res = 0`.
  - For k from 60 down to 0:
    - If bit k of `res` is 0, do `res ^= basis[k]`. Because `basis[k]` has its highest set bit at k, this raises bit k from 0 to 1 and never decreases `res`. (Equivalently: include `basis[k]` whenever `(res XOR basis[k]) > res`.)
  - At the end, `res` is the maximum XOR one can achieve.

Time Complexity:
  - Building the basis: O(N*B), B=61.
  - Querying max XOR: O(B).
  This is efficient for N <= 100.

## 4. C++ Implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int64_t> a;
int64_t basis[64];

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void add(int64_t x) {
    for(int l = 60; l >= 0; l--) {
        if(!(x & (1ll << l))) {
            continue;
        }
        if(basis[l] == 0) {
            basis[l] = x;
            return;
        }
        x ^= basis[l];
    }
}

void solve() {
    // Maximum XOR of a subsequence via a linear basis over GF(2).
    //
    // - basis[l] holds a reduced vector whose highest set bit is l. Inserting a
    //   number repeatedly clears its top bit using existing basis vectors; if a
    //   bit position is still free, the reduced number becomes the new basis
    //   vector there.
    //
    // - To maximise the XOR, scan bit positions from high to low and XOR in
    //   basis[l] whenever it would turn the current result's bit l from 0 to 1.

    for(int64_t x: a) {
        add(x);
    }

    int64_t res = 0;
    for(int l = 60; l >= 0; l--) {
        if(!(res & (1ll << l))) {
            res ^= basis[l];
        }
    }

    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

## 5. Python Implementation with Detailed Comments

```python
import sys

def add_to_basis(x, basis):
    """
    Insert integer x into the XOR-basis.
    'basis' is a dict mapping bit-position -> basis vector.
    """
    # Try to eliminate bits from 60 down to 0
    for bit in range(60, -1, -1):
        if ((x >> bit) & 1) == 0:
            continue
        # If no vector anchored at this bit, store x
        if bit not in basis:
            basis[bit] = x
            return
        # Otherwise eliminate that bit
        x ^= basis[bit]
    # If x becomes 0, it's linearly dependent and we discard it

def get_max_xor(basis):
    """
    Given the constructed basis, build the maximum possible XOR
    by greedily including basis vectors that increase the value.
    """
    ans = 0
    # Try to improve ans by XOR-ing with basis vectors from high to low
    for bit in sorted(basis.keys(), reverse=True):
        candidate = ans ^ basis[bit]
        if candidate > ans:
            ans = candidate
    return ans

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    nums = list(map(int, data[1:]))

    # Build the basis as a dict bit->vector
    basis = {}
    for x in nums:
        add_to_basis(x, basis)

    # Compute and print the result
    print(get_max_xor(basis))

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