#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#include "transfer.h"
#include <iostream>
using namespace std;
std::vector<int> get_attachment(std::vector<int> source) {
vt<int>res;
int xo = 0;
for(int i = 0; (1 << i) < sz(source); i++){
int bit = 0;
for(int j = 1; j <= sz(source); j++){
if((j >> i) & 1){
bit ^= source[j - 1];
}
}
res.pb(bit);
}
for(auto i: source)xo ^= i;
res.pb(xo);
//k = 9;
return(res);
}
std::vector<int> retrieve(std::vector<int> data) {
int n = ((sz(data) <= 100) ? 63 : 255);
int xo = 0;
for(int i = 0; i < n; i++)xo ^= data[i];
if(data.back() == xo){
vt<int>res;
for(int i = 0; i < n; i++)res.pb(data[i]);
return(res);
}
int mask = 0;
for(int i = 0; (1 << i) < n; i++){
int xo = 0;
for(int j = 1; j <= n; j++){
if((j >> i) & 1){
xo ^= data[j - 1];
}
}
if(xo != data[i + n]){
mask += (1 << i);
}
}
//cout << mask << " ";
if(mask != 0){
data[mask - 1] = !data[mask - 1];
}
vt<int>res;
for(int i = 0; i < n; i++)res.pb(data[i]);
return(res);
}
/*
static inline string run_scenario() {
int c;
cin >> c;
if (c < -1)
return "invalid corruption index";
string source_str;
cin >> source_str;
const int N = source_str.size();
const int max_attachment_size = 2*N;
vector<int> source;
for (int i=0; i<N; i++)
source.push_back(source_str[i]-'0');
vector<int> attachment = get_attachment(source);
if (int(attachment.size()) > max_attachment_size)
return "attachment too large";
for (int x : attachment)
if (x != 0 && x != 1)
return "invalid attachment integer value";
vector<int> data(source);
data.insert(data.end(), attachment.begin(), attachment.end());
if (c >= int(data.size()))
return "invalid corruption index";
if (c >= 0)
data[c] = 1-data[c];
vector<int> result_source = retrieve(data);
for(auto i: result_source)cout << i;
if (source != result_source)
return "wrong source retrieval";
return string("OK K=")+to_string(attachment.size());
}
//#include "transfer.h"
int main() {
int T;
cin >> T;
for (int scenario = 0; scenario < T; scenario++) {
string result = run_scenario();
cout << "scenario #" << scenario << ": " << result << endl;
}
return 0;
}
*/
