#include <bits/stdc++.h>
using namespace std;
#include "messy.h"
int cn;
vector<int> ans;
string st(vector<int> s){
string a;
for(auto i: s) a+=(char)('0'+i);
return a;
}
void add(vector<int> s){
add_element(st(s));
}
int check(vector<int> s){
return check_element(st(s));
}
void rr(int l, int r, vector<int> a, vector<int> b){
if(l+1==r){
ans[a[0]]=l;
ans[b[0]]=r;
}
else if(l<r){
int n= cn;
vector<int> t(n), x, y;
for(auto i: b) t[i]=1;
for(auto i: a){
t[i]=1;
if(check(t)) x.push_back(i);
else y.push_back(i);
t[i]=0;
}
int mid=(l+r)/2;
rr(l, mid, x, y);
x.clear(); y.clear();
for(auto i: b) t[i]=0;
for(auto i: a) t[i]=1;
for(auto i: b){
t[i]=1;
if(check(t)) x.push_back(i);
else y.push_back(i);
t[i]=0;
}
rr(mid+1, r, x, y);
}
}
std::vector<int> restore_permutation(int n, int w, int r) {
vector<int> s(n), t(n);
cn=n;
ans.resize(n);
for(int i=0; i<n/2; i++){
s[i]=1; add(s); s[i] = 0;
}
for(int i=n/2; i>1; i/=2){
for(int l=0; l<n; l+=2*i){
vector<int> t(n, 0);
for(int j=l; j<l+i; j++){
t[j] = 0;
}
for(int j=l+i; j<l+2*i; j++){
t[j]=1;
}
for(int j=l; j<l+i/2; j++){
t[j] = 1;
add(t);
t[j]=0;
}
for(int j=l; j<l+i; j++){
t[j] = 1;
}
for(int j=l+i; j<l+2*i; j++){
t[j]=0;
}
for(int j=l+i; j<l+3*i/2; j++){
t[j] = 1;
add(t);
t[j]=0;
}
}
}
compile_set();
vector<int> a, b;
for(int i=0; i<n; i++) s[i]=0;
for(int i=0; i<n; i++){
s[i]=1;
if(check(s)) a.push_back(i);
else b.push_back(i);
s[i]=0;
}
rr(0, n-1, a, b);
return ans;
}
/*
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
}*/
