#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
#define x first
#define y second
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
const char en='\n';
#include "messy.h"
void flip(string&a,int i)
{
a[i]='0'+'1'-a[i];
}
bool debug=0;
int rr,ww;
void add(string b)
{
++ww;
add_element(b);
if (debug) cout<<"added "<<b<<endl;
}
bool check(string b,int r)
{
++rr;
flip(b,r);
bool x=check_element(b);
flip(b,r);
return x;
}
vi restore_permutation(int n, int w, int r) {
//assert(n==8);
string b;
for (int i=0;i<n;++i) b.pb('0');
mt19937 rng1(1),rng2(1);
for (int i=1;i<n;i*=2)
{
string c=b;
for (int j=0;j<n;++j) if (j&i)
{
flip(b,j);
flip(c,j);
add(b);
flip(b,j);
}
int z=rng1();
if (z%2)
{
for (int j=0;j<n;++j) flip(c,j);
}
b=c;
}
compile_set();
string a;
for (int i=0;i<n;++i) a.pb('0');
vi ans(n);
for (int i=0;(1<<i)<n;++i)
{
if (debug) cout<<"a is "<<a<<endl;
string c=a;
for (int j=0;j<n;++j) if (check(a,j))
{
flip(c,j);
ans[j]+=1<<i;
}
int z=rng2();
if (z%2)
{
for (int j=0;j<n;++j) flip(c,j);
}
a=c;
}
vi bio(n);
for (auto a: ans) ++bio[a];
int z=0;
for (auto a: bio) z+=abs(a-1);
//assert(z<=2);
return ans;
}
