#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int N;
void _add_element(vector<int> x) {
string S(N, '0');
for(int i : x) S[i] = '1';
add_element(S);
}
bool _check_element(vector<int> x) {
string S(N, '0');
for(int i : x) S[i] = '1';
return check_element(S);
}
void add(int s, int e, vector<int> tmp) {
if (s == e) {
return;
}
int m = (s + e) >> 1;
for(int i = s; i <= m; i++) {
auto v = tmp;
v.push_back(i);
_add_element(v);
}
vector<int> v1, v2;
for(int i = s; i <= m; i++) v2.push_back(i);
for(int i = m+1; i <= e; i++) v1.push_back(i);
add(s, m, v1);
add(m+1, e, v2);
}
vector<int> check(int s, int e, vector<int> cand, vector<int> tmp) {
assert(int(cand.size()) == e - s + 1);
if(s == e) return cand;
vector<vector<int>> ok(2);
for(int i : cand) {
auto v = tmp;
v.push_back(i);
ok[!_check_element(v)].push_back(i);
}
int m = (s + e) >> 1;
auto l = check(s, m, ok[0], ok[1]);
auto r = check(m+1, e, ok[1], ok[0]);
for(int i : r) l.push_back(i);
return l;
}
vector<int> restore_permutation(int n, int w, int r) {
N = n;
add(0, N-1, vector<int>());
compile_set();
vector<int> a(N);
iota(a.begin(), a.end(), 0);
return check(0, N-1, a, vector<int>());
}
