#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <set>
#include <map>
#include <random>
#include "messy.h"
using namespace std;
typedef int ll;
typedef vector<ll> vll;
typedef string s;
typedef list<ll> lll;
typedef pair<ll,ll> pll;
typedef set<ll> sll;
/*struct cmp {
bool operator() (pair<ll, lll::iterator> a, pair<ll, lll::iterator> b) const {return a.first < b.first;}
};
typedef set<pair<ll, lll::iterator>, cmp> spll;*/
typedef set<pll> spll;
#define rep(a,b,c) for(ll a = b; a < c; a++)
#define itr_rep(a,b,_type) for(_type::iterator a = b.begin(); a != b.end(); a++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
std::vector<int> restore_permutation(int n, int w, int r) {
vll perm;
perm.clear();
s inp;
rep(i,0,n) {
inp.pb('0');
}
rep(i,0,n) {
inp[i] = '1';
add_element(inp);
}
compile_set();
sll left;
left.clear();
rep(i,0,n) {
left.insert(i);
}
spll shuffle;
random_device rd;
s target;
rep(i,0,n) {target.pb('0');}
rep(i,0,n) {
shuffle.clear();
mt19937 generator(rd()+i);
itr_rep(itr,left,sll) {
shuffle.insert(mp(generator(),*itr));
}
rep(i,0,left.size()) {
ll curr = (*shuffle.begin()).second;
//cout << "curr: " << curr << endl;
target[curr] = '1';
if (check_element(target)) {
perm.pb(curr);
left.erase(curr);
break;
}
target[curr] = '0';
shuffle.erase(shuffle.begin());
}
shuffle.clear();
}
/*rep(i,0,n) {cout << perm[i] << " ";}
cout << endl;*/
// need to invert perm bc i am stupid;
vll actual;
actual.resize(n,0);
rep(i,0,n) {
actual[perm[i]] = i;
}
return actual;
}
