#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
namespace permutation {
vector<int> construct_permutation_slow(long long k) {
vector<int> ret(k - 1);
for (int i = 0; i < k - 1; i++)
ret[i] = k - 2 - i;
return ret;
}
const array<int, 5> primes = {2, 3, 5, 7, 11};
vector<int> construct_permutation_dumb(long long k) {
if (k <= 3)
return construct_permutation_slow(k);
for (int p : primes) {
if (k % p != 0 || k == p)
continue;
auto ret = construct_permutation_dumb(k / p);
auto tem = construct_permutation_dumb(p);
int r = ret.size();
for (int t : tem)
ret.push_back(t + r);
return ret;
}
auto ret = construct_permutation_dumb(k / 2);
ret.push_back(ret.size());
ret.insert(ret.begin(), ret.size());
return ret;
}
}
vector<int> construct_permutation(long long k) {
if (k <= 90)
return permutation::construct_permutation_slow(k);
else
return permutation::construct_permutation_dumb(k);
}
