#include <bits/stdc++.h>

#include "perm.h"

using namespace std;

void mul2(vector<int> &p) {
    p.emplace_back((int) p.size());
}

void add1(vector<int> &p) {
    for (int &i: p) i++;
    p.emplace_back(0);
}

bool isGood(vector<int> p) {
    int pos1, pos0;
    for (int i = 0; i < (int) p.size(); i++) {
        if (p[i] == 1) pos1 = i;
        if (p[i] == 0) pos0 = i;
    }
    return pos1 < pos0;
}

std::vector<int> construct_permutation(long long k) {
    if (k <= 91) {
        vector<int> res(k - 1);
        iota(res.begin(), res.end(), 0);
        reverse(res.begin(), res.end());
        return res;
    }
    vector<int> operations;
    while (k > 1) {
        operations.emplace_back(k % 4);
        k /= 4;
    }
    vector<int> res;
    if (operations.back() == 0) res = {0, 1};
    else if (operations.back() == 1) res = {1, 2, 0};
    else if (operations.back() == 2) res = {1, 0, 2};
    else res = {2, 1, 3, 0};
    operations.pop_back();
    reverse(operations.begin(), operations.end());
    for (int r: operations) {
        if (r == 0) {
            mul2(res), mul2(res);
        } else if (r == 1) {
            mul2(res), mul2(res), add1(res);
        } else if (r == 2) {
            mul2(res), add1(res), mul2(res);
        } else {
            if (isGood(res)) {
                mul2(res), mul2(res);
                for (int &i: res)
                    if (i > 1) ++i;
                res.emplace_back(2);
            } else {
                mul2(res), add1(res), mul2(res), add1(res);
            }
        }
    }
    return res;
}