#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;
	}

	vector<int> construct_permutation_mid(long long k) {
		int n = __lg(k);
		vector<int> ret(n);
		iota(ret.begin(), ret.end(), 0);
		for (int b = n - 1; b >= 0; b--)
			if (k >> b & 1)
				ret.insert(ret.begin() + b, n++);
		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);
}