#include <iostream>
#include "algorithm"
#include "array"
#include "bitset"
#include "climits"
#include "cmath"
#include "deque"
#include "iomanip"
#include "map"
#include "numeric"
#include "set"
#include "transfer.h"
#include "vector"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
vector<int> rearange(vector<int> a, int k) {
int n = sz(a) - k;
vector<int> b(sz(a));
for (int i = 0; i < k; i++) {
b[1 << i] = 1;
}
int ind = 0;
for (int i = 0; i < sz(a) - k; i++) {
while (b[ind] == 1) {
ind++;
}
if (ind < sz(b)) {
b[ind] = a[i];
ind++;
} else {
cout << "FAC" << ind << endl;
}
}
for (int i = 0; i < k; i++) {
b[1 << i] = a[n + i];
}
return b;
}
vector<int> rearange2(vector<int> a, int k) {
int n = sz(a) - k;
vector<int> b(sz(a)), c = b;
for (int i = 0; i < k; i++) {
b[1 << i] = 1;
}
int ind = 0;
for (int i = 0; i < sz(a) - k; i++) {
while (ind < sz(b) and b[ind] == 1) {
ind++;
}
if (ind < sz(c))
c[i] = a[ind];
else {
cout << "BLYA" << ind << endl;
}
ind++;
}
for (int i = 0; i < k; i++) {
c[n + i] = a[1 << i];
}
return c;
}
void addzer(vector<int> &a) {
vector<int> b = {0};
for (auto i : a) {
b.push_back(i);
}
swap(a, b);
}
vector<int> get_attachment(vector<int> source) {
addzer(source);
int n = sz(source);
int k = 7;
if (n > 90)
k = 9;
vector<int> beba(k);
for (int i = 0; i < k; i++) {
source.push_back(0);
}
// for (auto i : source)
// cout << i;
// cout << '\n';
source = rearange(source, k);
// source = rearange2(source, k);
// for (auto i : source)
// cout << i;
// cout << '\n';
for (int i = 0; i < k; i++) {
for (int j = 0; j < n + k; j++) {
if (j & (1 << i))
beba[i] ^= source[j];
}
}
return beba;
}
vector<int> retrieve(vector<int> data) {
addzer(data);
int n = sz(data);
int k = 7;
if (n > 90)
k = 9;
n -= k;
for (int i = n; i < n + k; i++) {
// data[i] = 2 + i - n;
}
// for (auto i : data)
// cout << i;
// cout << '\n';
data = rearange(data, k);
// for (auto i : data)
// cout << i;
// cout << '\n';
// cout << n << ' ' << k << '\n';
vector<int> beba(k);
int ind = 0;
for (int i = 0; i < k; i++) {
for (int j = 0; j < n + k; j++) {
if (j & (1 << i))
beba[i] ^= data[j];
}
if (beba[i] != 0)
ind += (1 << i);
}
// cerr << ind << endl;
// exit(0);
data[ind] ^= 1;
data = rearange2(data, k);
vector<int> res;
for (int i = 1; i < n; i++) {
res.push_back(data[i]);
// cout << data[i];
}
// cout << endl;
return res;
}
#ifdef LOCAL
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);
if (source != result_source)
return "wrong source retrieval";
return string("OK K=") + to_string(attachment.size());
}
int main() {
freopen("inp.txt", "r", stdin);
int T;
cin >> T;
for (int scenario = 0; scenario < T; scenario++) {
string result = run_scenario();
cout << "scenario #" << scenario << ": " << result << endl;
}
return 0;
}
#endif
