#include <bits/stdc++.h>
using namespace std;
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"
const int N = 1e6 + 9;
int n, a[N];
int rangexor (const vector <int> &v, int be, int en){
int res = 0; for (int i = be; i < en; i++) res ^= v[i]; return res;
}
int bitxor (const vector <int> &v, int n, int idx){
int res = 0; for (int i = 0; i < n; i++) if ((i + 1) >> idx & 1) res ^= v[i]; return res;
}
int lg (int val){
int x = 0; for (int i = val; i > 0; i >>= 1) x++; return x;
}
vector <int> get_attachment (vector <int> source){
int n = source.size ();
int _lg = lg (n);
vector <int> ret;
for (int i = 0; i < _lg; i++) ret.push_back (bitxor (source, n, i));
int x = rangexor (ret, 0, _lg);
ret.push_back (x);
return ret;
}
vector <int> retrieve (vector <int> data){
int sz = data.size ();
int n = sz >> 1;
while (n + lg (n) + 1 < sz) n++;
vector <int> res (data.begin (), data.begin () + n);
vector <int> extra (data.begin () + n, data.end ());
int len = extra.size () - 1;
if (extra.back () != rangexor (extra, 0, len)) return res;
int must = 0;
for (int i = 0; i < len; i++) if (extra[i] != bitxor (res, n, i)) must |= (1 << i);
must--;
if (must >= 0) res[must] ^= 1;
return res;
}
// love you, noodles0428 <333
// tst25
