#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
/*void add_element(string x);
bool check_element(string x);
void compile_set();*/
bool debug = false;
void add_element2(int s, int e, int n){
if(s == e){return;}
int m = (s+e)>>1;
for(int i = s; i <= m; i ++){
string x = "";
for(int j = 0; j < n; j ++){
if(j < s || j > e || j == i){
x += '1';
}else{
x += '0';
}
}
if(debug){
printf("%s\n", x.c_str());
}
add_element(x);
}
add_element2(s, m, n);
add_element2(m+1, e, n);
}
int ans2[130];
void check_element2(int s, int e, int n, vector<int> possible){
if(debug){
printf("check_element2 s=%d e=%d n=%d possible=", s, e, n);
for(int i = 0; i < (int)possible.size(); i ++){
printf("%d ", possible[i]);
}
printf("\n");
}
if(s == e){
ans2[possible[0]] = s;
return;
}
int m = (s+e)>>1;
vector<int> possiblepos_1;
vector<int> possiblepos_2;
for(int i = 0; i < n; i ++){
if(binary_search(possible.begin(), possible.end(), i)){
// this position is what you want to query
string x;
for(int j = 0; j < n; j ++){
if(!binary_search(possible.begin(), possible.end(), j) || j == i){
x += '1';
}else{
x += '0';
}
}
if(debug){
printf("%s\n", x.c_str());
}
if(check_element(x)){
// hit: go to left
if(debug){
printf("s=%d e=%d left: %d\n", s, e, i);
}
possiblepos_1.push_back(i);
}else{
// miss: go to right
if(debug){
printf("s=%d e=%d right: %d\n", s, e, i);
}
possiblepos_2.push_back(i);
}
}
}
/*if(debug){
printf("check_element2 s=%d e=%d n=%d possiblepos_1=%d possiblepos_2=%d\n", s, e, n, (int)possiblepos_1.size(),
(int)possiblepos_2.size());
}*/
check_element2(s, m, n, possiblepos_1);
check_element2(m+1, e, n, possiblepos_2);
}
vector<int> restore_permutation(int _n, int w, int r) {
int n = _n;
if(debug){
printf("Elements to be added\n");
}
add_element2(0, n-1, n);
compile_set();
if(debug){
printf("Set compiled successfully\n");
}
vector<int> everything;
for(int i = 0; i < n; i ++){
everything.push_back(i);
}
check_element2(0, n-1, n, everything);
vector<int> ans;
for(int i = 0; i < n; i ++){
ans.push_back(ans2[i]);
}
return ans;
}
