#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
typedef long long ll;
vector<int> restore_permutation(int n, int w, int r) {
string s0 = "", s1 = "";
for (int i = 0; i < n; i++) {
s0 += '0';
s1 += '1';
}
string s;
s = s1; s[n-1] = '0';
add_element(s);
s = s1; s[n-2] = '0';
add_element(s);
s = s1; s[n-3] = '0';
add_element(s);
s = s1; s[n-1] = s[n-2] = '0';
add_element(s);
s = s1; s[n-1] = s[n-3] = '0';
add_element(s);
s = s1; s[n-2] = s[n-3] = '0';
add_element(s);
s = s0; s[n-1] = '1';
add_element(s);
s[n-2] = '1';
add_element(s);
vector<string> sBits;
s = s0; s[n-1] = '1';
sBits.push_back(s);
s = s0; s[n-2] = '1';
sBits.push_back(s);
s = s0; s[n-1] = s[n-2] = '1';
sBits.push_back(s);
s = s0; s[n-3] = '1';
sBits.push_back(s);
s = s0; s[n-1] = s[n-3] = '1';
sBits.push_back(s);
s = s0; s[n-2] = s[n-3] = '1';
sBits.push_back(s);
s = s0; s[n-1] = s[n-2] = s[n-3] = '1';
sBits.push_back(s);
for (int i = 0; i < n-3; i++) {
for (int b = 0; b < 7; b++) {
if ((i >> b) & 1) {
s = sBits[b];
s[i] = '1';
add_element(s);
}
}
}
compile_set();
vector<ll> G(n);
for (int i = 0; i < n; i++) G[i] = i;
mt19937 mt(time(0));
shuffle(G.begin(), G.end(), mt);
vector<int> res(n);
vector<ll> c(3, -1);
ll ptr = 0;
s = s1;
for (int i1 = 0; i1 < n-1; i1++) {
int i = G[i1];
s[i] = '0';
bool has = check_element(s);
if (has) {
c[ptr++] = i;
}
if (!has || ptr > 1) {
s[i] = '1';
}
if (ptr == 3) break;
}
if (ptr < 3) c[2] = G[n-1];
s = s0;
s[c[0]] = '1';
bool v = check_element(s);
vector<ll> ctrl(3);
if (!v) {
s = s0;
s[c[1]] = '1';
v = check_element(s);
if (!v) {
ctrl[0] = c[2];
s = s0;
s[ctrl[0]] = s[c[0]] = '1';
v = check_element(s);
if (!v) {
ctrl[1] = c[1];
ctrl[2] = c[0];
}
else {
ctrl[1] = c[0];
ctrl[2] = c[1];
}
}
else {
ctrl[0] = c[1];
s = s0;
s[ctrl[0]] = s[c[0]] = '1';
v = check_element(s);
if (!v) {
ctrl[1] = c[2];
ctrl[2] = c[0];
}
else {
ctrl[1] = c[0];
ctrl[2] = c[2];
}
}
}
else {
ctrl[0] = c[0];
s = s0;
s[ctrl[0]] = s[c[1]] = '1';
v = check_element(s);
if (!v) {
ctrl[1] = c[2];
ctrl[2] = c[1];
}
else {
ctrl[1] = c[1];
ctrl[2] = c[2];
}
}
vector<bool> isCtrl(n);
isCtrl[ctrl[0]] = true;
isCtrl[ctrl[1]] = true;
isCtrl[ctrl[2]] = true;
sBits.clear();
s = s0; s[ctrl[0]] = '1';
sBits.push_back(s);
s = s0; s[ctrl[1]] = '1';
sBits.push_back(s);
s = s0; s[ctrl[0]] = s[ctrl[1]] = '1';
sBits.push_back(s);
s = s0; s[ctrl[2]] = '1';
sBits.push_back(s);
s = s0; s[ctrl[0]] = s[ctrl[2]] = '1';
sBits.push_back(s);
s = s0; s[ctrl[1]] = s[ctrl[2]] = '1';
sBits.push_back(s);
s = s0; s[ctrl[0]] = s[ctrl[1]] = s[ctrl[2]] = '1';
sBits.push_back(s);
unordered_set<ll> missing;
for (int i = 0; i < n-3; i++) {
missing.insert(i);
}
shuffle(G.begin(), G.end(), mt);
for (int i1 = 0; i1 < n; i1++) {
int i = G[i1];
if (isCtrl[i]) continue;
ll val = 0;
for (int b = 6; b >= 0; b--) {
bool h0 = false, h1 = false;
for (auto &e : missing) {
if ((e >> b) & 1) h1 = true;
else h0 = true;
}
if (!h0) {
val <<= 1;
val |= 1;
continue;
}
else if (!h1) {
val <<= 1;
continue;
}
s = sBits[b];
s[i] = '1';
v = check_element(s);
val <<= 1;
val |= v;
}
res[i] = val;
missing.erase(val);
}
res[ctrl[0]] = n-1;
res[ctrl[1]] = n-2;
res[ctrl[2]] = n-3;
return res;
}
