#include "messy.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
/*
set<string> s;
vec<int> pp;
void add_element(string x) {
string x2;
For(i, pp.size()) x2.push_back(x[i]);
For(i, pp.size()) {
x2[pp[i]] = x[i];
}
s.insert(x2);
return;
}
bool check_element(string x) {
return (s.find(x) != s.end());
}
void compile_set() {
return;
}
*/
void pridavaj(int a, int b, int n) {
if (a == b) {
return;
}
string x;
For(i, n) x.push_back('1');
ffor(i, a, b + 1) x[i] = '0';
for (int j = a; j <= (a + b) / 2; j++) {
x[j] = '1';
add_element(x);
x[j] = '0';
}
pridavaj(a, (a + b) / 2, n);
pridavaj((a + b) / 2 + 1, b, n);
return;
}
void zisti(vec<int>&p, int a, int b, int n, set<int>m) {
if (a == b) {
p[a] = *m.begin();
return;
}
string x;
For(i, n) x.push_back('1');
for(auto i : m) x[i] = '0';
set<int> m2;
for(auto i : m){
x[i] = '1';
bool je = check_element(x);
if(je) m2.insert(i);
x[i] = '0';
}
for (auto i : m2) m.erase(i);
zisti(p, a, (a + b) / 2, n, m2);
zisti(p, (a + b) / 2 + 1, b, n, m);
return;
}
vec<int> restore_permutation(int n, int w, int r) {
int log = 0;
while ((1 << log) < n) log++;
vec<int> p(n, -1);
set<int>m;
For(i, n) m.insert(i);
string x;
For(i, n) x.push_back('0');
pridavaj(0, n-1, n);
compile_set();
zisti(p, 0, n - 1, n, m);
return p;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
pp.resize(n);
For(i, n) cin >> pp[i];
vec<int> p = restore_permutation(n, 0, 0);
For(i, p.size()) cout << p[i] << " \n"[i == (p.size() - 1)];
return 0;
}*/
