#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(), order_of_key()
typedef long long ll;
typedef long double dd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<dd, dd> pdd;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<dd> vdd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vdd> vvdd;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef vector<vpdd> vvpdd;
typedef vector<bool> vb;
const int inf = 1 << 30;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ffor(i, a, b) for(ll i = a; i < b; i++)
#define forin(x, a) for (auto &x: a)
#define all(x) x.begin(), x.end()
#ifdef TEST
#define dbg(x) cout << #x << ": " << x << '\n';
#define dbgc(x) cout << #x << ":"; forin(a, x) { cout << " " << a; } cout << endl;
#define tassert(x) assert(x);
#else
#define dbg(x)
#define dbgc(x)
#define tassert(x)
#endif
string con1(int a, int b) {
string res(8, '0');
res[a] = '1';
res[b] = '1';
return res;
}
string cones(vii a) {
string res(32, '1');
forin(x, a) {
res[x] = '0';
}
return res;
}
string czeros(vii a) {
string res(32, '0');
forin(x, a) {
res[x] = '1';
}
return res;
}
std::vector<int> restore_permutation(int n, int w, int r) {
if (n == 8) {
add_element("01000000");
add_element("00010000");
add_element("00000100");
add_element("00000001");
add_element("11011111");
add_element("11101111");
add_element("11111101");
add_element("11111110");
add_element("00001100");
add_element("00001010");
add_element("00001001");
add_element("00000110");
add_element("00000101");
add_element("00000011");
compile_set();
string ones(8, '1'), zeros(8, '0');
vii g[4];
rep(i, 8) {
int curr = 0;
zeros[i] = '1';
ones[i] = '0';
if (check_element(zeros)) {
curr |= 1;
}
if (check_element(ones)) {
curr |= 2;
}
zeros[i] = '0';
ones[i] = '1';
g[curr].emplace_back(i);
}
vii res(8, -1);
if (check_element(con1(g[0][0], g[1][0]))) {
res[g[0][0]] = 4;
res[g[0][1]] = 0;
res[g[1][0]] = 5;
res[g[1][1]] = 1;
} else if (check_element(con1(g[0][1], g[1][0]))) {
res[g[0][0]] = 0;
res[g[0][1]] = 4;
res[g[1][0]] = 5;
res[g[1][1]] = 1;
} else if (check_element(con1(g[0][0], g[1][1]))) {
res[g[0][0]] = 4;
res[g[0][1]] = 0;
res[g[1][0]] = 1;
res[g[1][1]] = 5;
} else {
res[g[0][0]] = 0;
res[g[0][1]] = 4;
res[g[1][0]] = 1;
res[g[1][1]] = 5;
}
if (check_element(con1(g[2][0], g[3][0]))) {
res[g[2][0]] = 6;
res[g[2][1]] = 2;
res[g[3][0]] = 7;
res[g[3][1]] = 3;
} else if (check_element(con1(g[2][1], g[3][0]))) {
res[g[2][0]] = 2;
res[g[2][1]] = 6;
res[g[3][0]] = 7;
res[g[3][1]] = 3;
} else if (check_element(con1(g[2][0], g[3][1]))) {
res[g[2][0]] = 6;
res[g[2][1]] = 2;
res[g[3][0]] = 3;
res[g[3][1]] = 7;
} else {
res[g[2][0]] = 2;
res[g[2][1]] = 6;
res[g[3][0]] = 3;
res[g[3][1]] = 7;
}
return res;
}
else if (n == 32) {
string ones(32, '1'), zeros(32, '0');
rep(i, n) {
if (i & 1) {
add_element(czeros({i}));
}
if (i & 2) {
add_element(cones({i}));
}
}
rep(i, 4) {
add_element(czeros({4 | i, 12 | i}));
add_element(czeros({4 | i, 20 | i}));
add_element(czeros({4 | i, 28 | i}));
add_element(czeros({12 | i, 20 | i}));
add_element(czeros({12 | i, 28 | i}));
add_element(czeros({20 | i, 28 | i}));
}
rep(i, 4) {
add_element(cones({8 | i, 12 | i}));
add_element(cones({8 | i, 24 | i}));
add_element(cones({8 | i, 28 | i}));
add_element(cones({12 | i, 24 | i}));
add_element(cones({12 | i, 28 | i}));
add_element(cones({24 | i, 28 | i}));
}
rep(i, 4) {
add_element(czeros({16 | i, 20 | i, 24 | i, 28 | i}));
}
compile_set();
vii inv(32, -1);
int rem[2][2] = {{16, 16}, {16, 16}};
vii g[4];
rep(i, 32) {
int curr = 0;
rep(j, 2) {
if (!rem[j][0]) {
curr |= (j + 1);
} else if (rem[j][1]) {
if (j) {
if (check_element(cones({i}))) {
curr |= (j + 1);
rem[j][1]--;
} else {
rem[j][0]--;
}
} else {
if (check_element(czeros({i}))) {
curr |= (j + 1);
rem[j][1]--;
} else {
rem[j][0]--;
}
}
}
}
g[curr].emplace_back(i);
inv[i] = curr;
}
rep(i, 4) {
auto &cg = g[i];
int j = 0, k = 1;
bool ff = false;
while (j < 7) {
if (j == 6) {
tassert(ff);
inv[cg[6]] |= 4;
inv[cg[7]] |= 4;
break;
}
if (!ff && j == 4) {
inv[cg[4]] |= 4;
inv[cg[5]] |= 4;
inv[cg[6]] |= 4;
inv[cg[7]] |= 4;
break;
}
if (check_element(czeros({cg[j], cg[k]}))) {
if (ff) {
inv[cg[j]] |= 4;
inv[cg[k]] |= 4;
break;
} else {
ff = true;
inv[cg[j]] |= 4;
inv[cg[k]] |= 4;
j = k + 1;
k = j + 1;
}
} else if (k == 7 || (!ff && k == 5)){
j++;
k = j + 1;
} else {
k++;
}
}
}
rep(i, 4) {
auto &cg = g[i];
int j = 0, k = 1;
bool ff = false;
while (j < 7) {
if (j == 6) {
tassert(ff);
inv[cg[6]] |= 8;
inv[cg[7]] |= 8;
break;
}
if (!ff && j == 4) {
inv[cg[4]] |= 8;
inv[cg[5]] |= 8;
inv[cg[6]] |= 8;
inv[cg[7]] |= 8;
break;
}
if (check_element(cones({cg[j], cg[k]}))) {
if (ff) {
inv[cg[j]] |= 8;
inv[cg[k]] |= 8;
break;
} else {
ff = true;
inv[cg[j]] |= 8;
inv[cg[k]] |= 8;
j = k + 1;
k = j + 1;
}
} else if (k == 7 || (!ff && k == 5)){
j++;
k = j + 1;
} else {
k++;
}
}
}
rep(i, 4) {
vii g2[4];
forin(x, g[i]) {
g2[inv[x] >> 2].emplace_back(x);
}
bool found = false;
rep(j, 15) {
vii curr;
int k = j;
rep(l, 4) {
curr.emplace_back(g2[l][k & 1]);
k >>= 1;
}
if (check_element(czeros(curr))) {
found = true;
forin(x, curr) {
inv[x] |= 16;
}
break;
}
}
if (!found) {
rep(j, 4) {
inv[g2[j][1]] |= 16;
}
}
}
vii res(32);
rep(i, 32) {
res[inv[i]] = i;
}
return inv;
}
add_element("0");
compile_set();
check_element("0");
return std::vector<int>();
}
