## 1. Abridged Problem Statement

Given N (<=100) non-negative integers A_1...A_n (each up to 10^18), pick 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. Detailed Editorial

We want to maximize XOR over any subset of the input numbers. XOR forms a vector space over GF(2) on the bit-level, so the problem reduces to finding the maximum possible linear combination (over GF(2)) of the given "bit-vectors". The standard technique is to build a **basis** of these vectors in decreasing bit-order via a process akin to Gaussian elimination. Once we have a basis, we can greedily construct the maximum XOR:

### Step A: Build a XOR-basis ("linear basis")

- Maintain an array `basis[l]` for bit-positions l = 0...60, each slot either 0 (empty) or storing one basis vector whose highest set-bit is l.
- To **insert** a new number x into the basis:
  - For bits l from high to low:
    - If bit l of x is 0, skip.
    - If bit l of x is 1 and `basis[l]` is empty, set `basis[l] = x` and stop.
    - If bit l of x is 1 and `basis[l]` is nonzero, replace x with `x XOR basis[l]` and continue.
  - This ensures that at the end, all basis vectors are independent and each occupies a unique leading bit.

### Step B: Compute the maximum XOR you can form

- Initialize an accumulator `res = 0`.
- Iterate l from highest bit to lowest:
  - If bit l of `res` is currently 0, XOR in `basis[l]`. Since `basis[l]` has its highest set bit exactly at l, this turns bit l of `res` from 0 to 1, which only increases `res`. (Equivalently: XOR `basis[l]` in whenever `(res XOR basis[l]) > res`.)
- The result is the maximum subset-XOR.

### Complexities

- Building the basis: O(N * B) where B ~ 60 (max bits).
- Querying max XOR: O(B).
- For N <= 100 and B = 60 this is instantaneous.



## 3. C++ Solution

```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;
}
```



## 4. Python Solution

```python
import sys

def add_to_basis(x, basis):
    """
    Try to insert integer x into the XOR-basis.
    'basis' is a dict mapping bit-position -> basis vector.
    """
    # Process bits from high to low
    for bit in reversed(range(61)):  # bits 0..60
        if not (x >> bit) & 1:
            continue
        if bit not in basis:
            # Found an empty slot: store x here
            basis[bit] = x
            return
        # Eliminate this bit using existing basis vector
        x ^= basis[bit]
    # If x reduces to 0, it's dependent and we discard it

def get_max_xor(basis):
    """
    Given a basis, greedily build the maximum XOR.
    """
    ans = 0
    # Try to improve ans by XORing with each basis vector in descending bit-order
    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:]))

    basis = {}
    # Build the basis
    for x in nums:
        add_to_basis(x, basis)

    # Print the maximum subset XOR
    print(get_max_xor(basis))

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



## 5. Compressed Editorial

- View each number as a bit-vector of length <=61.
- Build an independent set of vectors ("basis") by iteratively inserting each number: if its highest set bit collides with an existing basis vector, XOR it out and continue; otherwise add it.
- To get the maximum XOR of any subset, start from 0 and for each basis vector (highest-bit first), XOR it in if it increases the current value.
- Time O(N*B + B) with B ~ 60 suffices for N <= 100.
