#include <bits/stdc++.h>
using namespace std;
void add_element(std::string x);
bool check_element(std::string x);
void compile_set();
int n;
int i, j;
string get(int l, int r){
string s = string(n, '0');
for(int i = l; i <= r; i++) s[i] = '1';
return s;
}
void calc1(int l = 0, int r = n - 1){
if(l == r) return;
int mid = (l + r) >> 1;
add_element(get(l, mid));
calc1(l, mid);
calc1(mid + 1, r);
}
void calc2(int l = 0, int r = n - 1){
if(l == r) return;
int mid = (l + r) >> 1;
if(!check_element(get(l, mid))){
for(i = l; i <= mid; i++){
for(j = mid + 1; j <= r; j++){
string s = get(l, mid);
swap(s[i], s[j]);
if(check_element(s)){
return;
}
}
}
}
calc2(l, mid); calc2(mid+1, r);
}
vector<int> restore_permutation(int N, int w, int r){
n = N;
calc1();
compile_set();
calc2();
vector<int> ans;
for(int i = 0; i < n; i++){
ans.push_back(i);
}
swap(ans[i], ans[j]);
return ans;
}
