#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <iomanip>
#include <queue>
#include <cassert>
#include <complex>
#include <cstring>
#include <memory>
#include <bitset>
#include <sstream>
#include <cmath>
#include <numeric>
#include <numbers>
#include <fstream>
#include "messy.h"
using namespace std;
#ifndef template
#ifndef define
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define pi pair<int, int>
#define nl cout << '\n';
#define x first
#define y second
#define cbit(x) __builtin_popcountll(x)
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng)
#define siz(x) (int)x.size()
#endif
#ifndef print
void print(size_t x) {cout << x << ' ';}
void print(int x) {cout << x << ' ';}
void print(long long x) {cout << x << ' ';}
void print(float x) {cout << x << ' ';}
void print(long double x) {cout << x << ' ';}
void print(char x) {cout << x << ' ';}
void print(const char* x) {cout << x << ' ';}
void print(bool x) {cout << x << ' ';}
void print(string &x) {cout << x << ' ';}
template<typename T, typename V>
void print(pair<T, V> &p) {print(p.x); print(p.y);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
for (int i = 0; i < v.size(); i++){
for (int j = 0; j < v[i].size(); j++)
print(v[i][j]);
nl;
}
}
template <typename T, typename... V>
void print(T t, V&&... v) {print(t); print(v...);}
#endif
#ifndef read
void read(int &x) {cin >> x;}
void read(long long &x) {cin >> x;}
void read(unsigned &x) {cin >> x;}
void read(unsigned long long &x) {cin >> x;}
void read(float &x) {cin >> x;}
void read(long double &x) {cin >> x;}
void read(char &x) {cin >> x;}
void read(string &x) {cin >> x;}
void read(bool &x) {cin >> x;}
template<typename T>
void read(vector<T> &v) {
for (int i = 0; i < v.size(); i++)
read(v[i]);
}
template <typename T, typename... V>
void read(T &t, V&... v) {read(t); read(v...);}
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool maxi(T& a, const T& b) {
return a < b ? a = b, 1 : 0;
}
template<class T> bool mini(T& a, const T& b) {
return a > b ? a = b, 1 : 0;
}
template<class... Args>
auto vec(size_t n, Args&&... args) {
if constexpr(sizeof...(args) == 1)
return vector(n, args...);
else
return vector(n, vec(args...));
}
#endif
using namespace std;
const ll inf = 1e18;
const ll def = 1e5+1;
const ll mod = 1e9;
using namespace std;
// namespace helper {
// set<string> set_;
// bool compiled = false;
// int n;
// vector<int> p;
// int w;
// int r;
// int read_int() {
// int x;
// cin >> x;
// return x;
// }
// }
// using namespace helper;
// // A convenience function.
// int get_p(int i) {
// int ret = p[i];
// return ret;
// }
// void wa() {
// printf("WA\n");
// exit(0);
// }
// bool check(const string& x) {
// if ((int)x.length() != n) {
// return false;
// }
// for (int i = 0; i < n; i++) {
// if (x[i] != '0' && x[i] != '1') {
// return false;
// }
// }
// return true;
// }
// void add_element(string x) {
// print("added", x); nl;
// if (--w < 0 || compiled || !check(x)) {
// wa();
// }
// set_.insert(x);
// }
// bool check_element(string x) {
// print("checked", x, "-");
// if (--r < 0 || !compiled || !check(x)) {
// wa();
// }
// bool res = set_.count(x);
// if (res)
// print("yes");
// else
// print("no");
// nl;
// return res;
// }
// void compile_set() {
// if (compiled) {
// wa();
// }
// compiled = true;
// set<string> compiledSet;
// string compiledElement = string(n, ' ');
// for (set<string>::iterator it = set_.begin(); it != set_.end(); it++) {
// string s = *it;
// for (int i = 0; i < n; i++) {
// compiledElement[i] = s[get_p(i)];
// }
// compiledSet.insert(compiledElement);
// }
// set_ = compiledSet;
// }
vector<int> restore_permutation(int n, int w, int r){
int k = 0, crr = 1;
while (crr <= n){
crr *= 2;
k++;
}
string empty = "";
for (int i = 0; i < n; i++)
empty += '0';
for (int i = k - 1; i >= 1; i--){
int len = 1 << i;
for (int j = 0; j < n; j += len){
int l = j, r = l + len - 1;
string base = empty;
for (int u = 0; u < n; u++){
if (u >= l && u <= r)
continue;
base[u] = '1';
}
for (int u = l; u <= (l + r) / 2; u++){
string s = base;
s[u] = '1';
add_element(s);
}
}
}
compile_set();
auto res = vec(n, make_pair(0, n - 1));
for (int i = k - 1; i >= 1; i--){
int len = 1 << i;
for (int j = 0; j < n; j += len){
int l = j, r = l + len - 1;
string base = empty;
int mid = (l + r) / 2;
vector<int> left;
for (int u = 0; u < n; u++){
if (res[u] != make_pair(l, r))
base[u] = '1';
else
left.push_back(u);
}
for (int u : left)
res[u] = {mid + 1, r};
for (int u : left){
string s = base;
s[u] = '1';
if (check_element(s))
res[u] = {l, mid};
}
}
}
vector<int> p(n);
for (int i = 0; i < n; i++)
p[i] = res[i].x;
return p;
}
/*
00000000
11110000
00001111
*/
// int32_t main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (ifstream("input.txt").good()){
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// }
// n = read_int();
// w = read_int();
// r = read_int();
// p = vector<int>(n);
// for (int i = 0; i < n; i++) {
// p[i] = read_int();
// }
// vector<int> answer = restore_permutation(n, w, r);
// if (answer.size() != n) {
// printf("WA\n");
// return 0;
// }
// printf("%d", answer[0]);
// for (int i = 1; i < n; i++) {
// printf(" %d", answer[i]);
// }
// printf("\n");
// return 0;
// }
