<|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.

350. XOR-omania
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Professor Vasechkin had a notebook with an outstanding set of non-negative integers A1, A2,..., An. Somehow the most remarkable fact that made this set so outstanding appeared to be the impossibility to find such a subset of two or more elements, that XOR of elements in the subset would equal to zero. One day the professor managed to create a new set of integers B1, B2,..., Bn(n-1)/2 through applying the XOR operations to all pairs of elements of A set. The set B was not written in any particular order. Unfortunately due to his natural absent-mindedness professor lost the A set and now he is very confused but still obliged to ask you of a considerable favor. Please restore the set in accordance with the remaining B set.
Input
The first line describes M — the amount of numbers in B set (1 ≤ M ≤ 100, M = N x (N - 1) / 2 for some number N). The second line describes M numbers — B1, B2,..., BM (0 ≤ Bi ≤ 231 - 1).

Output
Print the A set in one line through a blank. All elements of A should be from 0 to 231 - 1 inclusively. If there are several solutions of the problem, you can choose any of them. It is guaranteed that there exists at least one A set that satisfies the condition.

Example(s)
sample input
sample output
6
30 19 66 13 92 81
94 64 77 28

<|response|>
1. Abridged Problem Statement
You are given a multiset B of size M = n·(n–1)/2 containing all pairwise XORs Ai⊕Aj (i<j) of an unknown set A = {A1,...,An}, where the Ai are non-negative integers and no non-trivial subset of A has XOR = 0. Recover any valid A (order doesn’t matter).

2. Key Observations
- XOR on integers is vector addition over GF(2).
- “No subset XORs to 0” means the Ai are linearly independent vectors in GF(2)^31.
- If {X1,...,Xn} is a basis, then all Xi⊕Xj (i<j) appear exactly once among the pairwise XORs.
- Shifting every basis element by the same constant C (i.e., replacing Xi with Xi⊕C) does not change any pairwise XORs. In particular, we can WLOG include 0 in our reconstructed basis (we choose C = X1 to map X1→0).

3. Full Solution Approach
a. Read M and the list B of size M.
b. Recover n by solving n·(n–1)/2 = M, i.e. n = (1 + √(1+8M)) / 2.
c. Insert all values of B into a set `present` for fast membership tests.
d. Initialize:
   • ans = [0]       // our basis under construction, we force 0 as the first element
   • span = [0]      // list of all XORs of subsets of ans (its GF(2) span)
   • in_span = {0}   // set of all values reachable as XORs of a subset of ans
e. Iterate over each b in B (in arbitrary order):
   if b ∈ in_span, skip (b is already spanned; accepting it would create a zero-XOR subset).
   else check “compatibility”: for every a in ans, (b⊕a) must be in `present`.
   If the check passes, accept b as a new basis vector:
     – For each s in the current span list, compute t = b⊕s; if t∉in_span, add t to in_span and append t to span.
     – Append b to ans.
f. After scanning all of B, output the elements of ans. This is a valid reconstruction (it includes zero; you may optionally XOR all elements by any constant to shift away from zero).

Complexity:
- n ≤ 15 when M ≤ 100.
- Each candidate b tests O(n) lookups in `present`.
- Maintaining span and in_span costs O(2^n·n) overall.
- Total time is more than enough under the given constraints.

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 m, n;
vector<int> b;

void read() {
    cin >> m;
    b.resize(m);
    cin >> b;
    n = (1 + (int)sqrt(1 + 8 * m)) / 2;
}

void solve() {
    // B holds all M = n(n-1)/2 pairwise XORs of the unknown set A. Since any
    // pairwise XOR is unchanged by XOR-ing every element of A with the same
    // constant, we may fix the first reconstructed element to 0.
    //
    // - present = the multiset of values that appear in B (any reconstructed
    //   pairwise XOR must be one of these).
    //
    // - ans = the elements we have committed to (starting with 0), and span =
    //   the set of XORs of all subsets of ans (its linear span over GF(2)),
    //   used to detect when a new value is XOR-dependent on chosen ones.
    //
    // We scan the B values in order. We accept a candidate value v only when
    // it is not already in span (otherwise it would create a zero-XOR subset)
    // and v ^ a is a value present in B for every a already in ans, i.e. the
    // new pairwise XORs it introduces are all consistent with B. On accepting
    // v we extend span by XOR-ing v into every current span element and append
    // v to ans.

    set<int> present;
    for(int x: b) {
        present.insert(x);
    }

    vector<int> ans = {0}, span = {0};
    set<int> in_span = {0};

    for(int i = 0; i < m; i++) {
        if(in_span.count(b[i])) {
            continue;
        }

        bool ok = true;
        for(int a: ans) {
            if(!present.count(b[i] ^ a)) {
                ok = false;
            }
        }

        if(ok) {
            int sz = span.size();
            for(int x = 0; x < sz; x++) {
                int val = b[i] ^ span[x];
                span.push_back(val);
                in_span.insert(val);
            }

            ans.push_back(b[i]);
        }
    }

    cout << ans << '\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
```python
import math
import sys

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

    # Recover n from equation n*(n-1)/2 = M
    n = (1 + math.isqrt(1 + 8*M)) // 2

    # present: set of all given pairwise XORs
    present = set(Bs)

    # ans: our reconstructed basis, force 0 as first element
    ans = [0]
    # span: list of XORs of all subsets of current ans
    span = [0]
    # in_span: set of values reachable by XORing a subset of ans
    in_span = {0}

    # Try each candidate b in Bs
    for b in Bs:
        # If already spanned, skip
        if b in in_span:
            continue

        # Check compatibility: for every a in ans, must have b^a in present
        valid = True
        for a in ans:
            if (b ^ a) not in present:
                valid = False
                break
        if not valid:
            continue

        # Accept b as a new basis element
        old_span = span[:]       # snapshot of current subset-XORs
        for s in old_span:
            t = b ^ s
            if t not in in_span:
                in_span.add(t)
                span.append(t)

        ans.append(b)

    # Print the answer (contains zero)
    print(" ".join(map(str, ans)))

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