#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
int n;
vector<int> sol;
void add(int L, int R)
{
if(L == R) return;
int mid = (L+R)/2;
string base;
for(int i = 0; i< n; i++)
{
if(i< L || i> R) base += "1";
else base += "0";
}
for(int i = L; i<= mid; i++)
{
base[i] = '1';
add_element(base);
base[i] = '0';
}
add(L, mid); add(mid+1, R);
}
void solve(int L, int R, vector<int> possible, vector<int> know)
{
//know = position we are guaranteed to know will be 1 (outside of L, R)
if(L == R)
{
assert((int) possible.size() == 1);
sol[L] = possible[0];
return;
}
string base(n, '0');
for(auto x : know) base[x] = '1';
vector<int> trues;
vector<int> falses;
vector<int> tmp_1 = know, tmp_2 = know;
for(auto x : possible)
{
base[x] = '1';
bool result = check_element(base);
if(result) trues.pb(x);
else falses.pb(x);
base[x] = '0';
}
int mid = (L+R)/2;
for(auto x : falses) tmp_1.pb(x);
for(auto x : trues) tmp_2.pb(x);
solve(L, mid, trues, tmp_1);
solve(mid+1, R, falses, tmp_2);
}
vector<int> restore_permutation(int _n, int _w, int _r)
{
n = _n;
add(0, n-1);
sol.resize(n);
compile_set();
vector<int> tmp;
for(int i = 0; i< n; i++) tmp.pb(i);
solve(0, n-1, tmp, vector<int>());
vector<int> res(n);
for(int i = 0; i< n; i++) res[sol[i]] = i;
return res;
}
