#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
void find_writes(string s0, vector<int> Bq) {
int n =s0.length(), q =Bq.size();
if(q == 1) return;
for(int i =0; i < q/2; i++) {
string s =s0;
s[Bq[i]] ='1';
add_element(s);}
string s1 =s0, s2 =s0;
vector<int> Bq1,Bq2;
for(int i =0; i < q/2; i++) {
s1[Bq[i]] ='1';
Bq2.push_back(Bq[i]);}
for(int i =0; i < q/2; i++) {
s2[Bq[q/2+i]] ='1';
Bq1.push_back(Bq[q/2+i]);}
find_writes(s1,Bq1);
find_writes(s2,Bq2);}
void find_perm(string s0, vector<int> Bq, vector<int> Bres, vector<int> &P) {
int n =s0.length(), q =Bq.size();
/* for(int i =0; i < q; i++) cout << Bq[i] << " ";
cout << "\n";
for(int i =0; i < q; i++) cout << Bres[i] << " ";
cout << ".\n";
*/ if(q == 2) {
string s =s0;
s[Bres[0]] ='1';
if(check_element(s)) {
P[Bres[0]] =Bq[0];
P[Bres[1]] =Bq[1];}
else {
P[Bres[0]] =Bq[1];
P[Bres[1]] =Bq[0];}
return;}
vector<int> Bres1,Bres2;
for(int i =0; i < q; i++) {
string s =s0;
s[Bres[i]] ='1';
if(check_element(s)) Bres1.push_back(Bres[i]);
else Bres2.push_back(Bres[i]);}
vector<int> Bq1,Bq2;
string s1 =s0, s2 =s0;
for(int i =0; i < q/2; i++) Bq2.push_back(Bq[q/2+i]);
for(int i =0; i < q/2; i++) Bq1.push_back(Bq[i]);
for(int i =0; i < q/2; i++) s2[Bres1[i]] =s1[Bres2[i]] ='1';
find_perm(s1,Bq1,Bres1,P);
find_perm(s2,Bq2,Bres2,P);}
vector<int> restore_permutation(int n, int w, int r) {
int b =0;
while((1<<b) != n) b++;
vector<int> Bq;
string s0;
for(int i =0; i < n; i++) {
Bq.push_back(i);
s0 +="0";}
find_writes(s0,Bq);
compile_set();
vector<int> P(n);
find_perm(s0,Bq,Bq,P);
return P;}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlICJtZXNzeS5oIgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBmaW5kX3dyaXRlcyhzdHJpbmcgczAsIHZlY3RvcjxpbnQ+IEJxKSB7CglpbnQgbiA9czAubGVuZ3RoKCksIHEgPUJxLnNpemUoKTsKCWlmKHEgPT0gMSkgcmV0dXJuOwoJZm9yKGludCBpID0wOyBpIDwgcS8yOyBpKyspIHsKCQlzdHJpbmcgcyA9czA7CgkJc1tCcVtpXV0gPScxJzsKCQlhZGRfZWxlbWVudChzKTt9CglzdHJpbmcgczEgPXMwLCBzMiA9czA7Cgl2ZWN0b3I8aW50PiBCcTEsQnEyOwoJZm9yKGludCBpID0wOyBpIDwgcS8yOyBpKyspIHsKCQlzMVtCcVtpXV0gPScxJzsKCQlCcTIucHVzaF9iYWNrKEJxW2ldKTt9Cglmb3IoaW50IGkgPTA7IGkgPCBxLzI7IGkrKykgewoJCXMyW0JxW3EvMitpXV0gPScxJzsKCQlCcTEucHVzaF9iYWNrKEJxW3EvMitpXSk7fQoJZmluZF93cml0ZXMoczEsQnExKTsKCWZpbmRfd3JpdGVzKHMyLEJxMik7fQoKdm9pZCBmaW5kX3Blcm0oc3RyaW5nIHMwLCB2ZWN0b3I8aW50PiBCcSwgdmVjdG9yPGludD4gQnJlcywgdmVjdG9yPGludD4gJlApIHsKCWludCBuID1zMC5sZW5ndGgoKSwgcSA9QnEuc2l6ZSgpOwovKglmb3IoaW50IGkgPTA7IGkgPCBxOyBpKyspIGNvdXQgPDwgQnFbaV0gPDwgIiAiOwoJY291dCA8PCAiXG4iOwoJZm9yKGludCBpID0wOyBpIDwgcTsgaSsrKSBjb3V0IDw8IEJyZXNbaV0gPDwgIiAiOwoJY291dCA8PCAiLlxuIjsKKi8JaWYocSA9PSAyKSB7CgkJc3RyaW5nIHMgPXMwOwoJCXNbQnJlc1swXV0gPScxJzsKCQlpZihjaGVja19lbGVtZW50KHMpKSB7CgkJCVBbQnJlc1swXV0gPUJxWzBdOwoJCQlQW0JyZXNbMV1dID1CcVsxXTt9CgkJZWxzZSB7CgkJCVBbQnJlc1swXV0gPUJxWzFdOwoJCQlQW0JyZXNbMV1dID1CcVswXTt9CgkJcmV0dXJuO30KCXZlY3RvcjxpbnQ+IEJyZXMxLEJyZXMyOwoJZm9yKGludCBpID0wOyBpIDwgcTsgaSsrKSB7CgkJc3RyaW5nIHMgPXMwOwoJCXNbQnJlc1tpXV0gPScxJzsKCQlpZihjaGVja19lbGVtZW50KHMpKSBCcmVzMS5wdXNoX2JhY2soQnJlc1tpXSk7CgkJZWxzZSBCcmVzMi5wdXNoX2JhY2soQnJlc1tpXSk7fQoJdmVjdG9yPGludD4gQnExLEJxMjsKCXN0cmluZyBzMSA9czAsIHMyID1zMDsKCWZvcihpbnQgaSA9MDsgaSA8IHEvMjsgaSsrKSBCcTIucHVzaF9iYWNrKEJxW3EvMitpXSk7Cglmb3IoaW50IGkgPTA7IGkgPCBxLzI7IGkrKykgQnExLnB1c2hfYmFjayhCcVtpXSk7Cglmb3IoaW50IGkgPTA7IGkgPCBxLzI7IGkrKykgczJbQnJlczFbaV1dID1zMVtCcmVzMltpXV0gPScxJzsKCWZpbmRfcGVybShzMSxCcTEsQnJlczEsUCk7CglmaW5kX3Blcm0oczIsQnEyLEJyZXMyLFApO30KCnZlY3RvcjxpbnQ+IHJlc3RvcmVfcGVybXV0YXRpb24oaW50IG4sIGludCB3LCBpbnQgcikgewoJaW50IGIgPTA7Cgl3aGlsZSgoMTw8YikgIT0gbikgYisrOwoKCXZlY3RvcjxpbnQ+IEJxOwoJc3RyaW5nIHMwOwoJZm9yKGludCBpID0wOyBpIDwgbjsgaSsrKSB7CgkJQnEucHVzaF9iYWNrKGkpOwoJCXMwICs9IjAiO30KCWZpbmRfd3JpdGVzKHMwLEJxKTsKCiAgICBjb21waWxlX3NldCgpOwoKICAgIHZlY3RvcjxpbnQ+IFAobik7CiAgICBmaW5kX3Blcm0oczAsQnEsQnEsUCk7CgogICAgcmV0dXJuIFA7fQo=