// AM+DG
/*
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<bool> vb;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "messy.h"
void write(int orig_n, int n, int l, int r) {
string cur_mask(orig_n, '1');
LI(i, l, r + 1) {
cur_mask[i] = '0';
}
string to_push;
LI(i, 0, n >> 1) {
to_push = cur_mask;
to_push[i + l] = '1';
add_element(to_push);
}
if(n > 2) {
int m = (l + r) >> 1;
write(orig_n, n >> 1, l, m);
write(orig_n, n >> 1, m + 1, r); // This is starting to look like segtree code LOL
}
}
void solve(int orig_n, int n, int offset, const set<int>& inds, vi& ans) {
set<int> left;
set<int> right;
string base_mask(orig_n, '1');
for(int i : inds) {
base_mask[i] = '0';
}
string cur_mask;
for(int i : inds) {
cur_mask = base_mask;
cur_mask[i] = '1';
(check_element(cur_mask) ? left : right).insert(i);
}
if(n > 2) {
solve(orig_n, n >> 1, offset, left, ans);
solve(orig_n, n >> 1, offset + (n >> 1), right, ans);
} else {
// cout << "KIMI DAYO KIMI NANDAYO " << *(left.begin()) << " " << *(right.begin()) << endl;
// (If you're reading this, I was listening to YLIA OST while coding so yeah, haha)
// The thing in the left set is index offset
ans[*(left.begin())] = offset;
// The thing in the right set is index offset + (n >> 1)
ans[*(right.begin())] = offset + (n >> 1);
}
}
vi restore_permutation(int n, int w, int r) {
// Write Elements
write(n, n, 0, n - 1);
// Compile the set!
compile_set();
// Solve!
vi ans(n, -1);
set<int> inds;
LI(i, 0, n) inds.insert(i);
solve(n, n, 0, inds, ans);
// LI(i, 0, n) {
// cout << ans[i] << " ";
// }
// cout << endl;
return ans;
}
#ifdef DEBUG
int main() {
}
#endif
