#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include "messy.h"
using namespace std;
int N;
void send(int l, int r, int idx)
{
if(l == r)return;
string s;
for(int i = 1; i <= N; i++)
s += '0';
int mid = (l+r)/2;
if(idx == 1)
{
for(int i = 0; i <= mid; i++)
{
s[i] = '1';
///cout << s << endl;
add_element(s);
s[i] = '0';
}
send(l, mid, idx*2);
send(mid+1, r, idx*2+1);
return;
}
for(int i = 0; i < l; i++)
s[i] = '1';
for(int i = r+1; i < N; i++)
s[i] = '1';
///cout << l << " " << r << " " << s << endl;
for(int i = l; i <= mid; i++)
{
s[i] = '1';
///cout << s << endl;
add_element(s);
s[i] = '0';
}
send(l, mid, idx*2);
send(mid+1, r, idx*2+1);
}
vector <int> ans;
void solve(int l, int r, vector <int> v)
{
if(l == r)
{
ans[v[0]] = l;
return;
}
string s;
for(int i = 0; i < N; i++)
s += '1';
for(int i = 0; i < v.size(); i++)
s[v[i]] = '0';
///cout << l << " " << r << " " << s << endl;
vector <int> left, right;
for(int i = 0; i < v.size(); i++)
{
s[v[i]] = '1';
if(check_element(s) == true)left.push_back(v[i]);
else right.push_back(v[i]);
s[v[i]] = '0';
}
/*for(int i = 0; i < left.size(); i++)
cout << left[i] << " ";
cout << endl;
for(int i = 0; i < right.size(); i++)
cout << right[i] << " ";
cout << endl << endl;*/
int mid = (l+r)/2;
solve(l, mid, left);
solve(mid+1, r, right);
}
std::vector<int> restore_permutation(int n, int w, int r)
{
N = n;
send(0, n-1, 1);
compile_set();
vector <int> v;
for(int i = 0; i < n; i++)
ans.push_back(0);
for(int i = 0; i < n; i++)
v.push_back(i);
solve(0, n-1, v);
return ans;
}
