#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXV (1<<17)
vector<int> primos;
vector<int> dp[MAXV];
map<ll, vector<int>> pans;
int initted=0;
int count_increasing_b(const vector<int>& v) {
vector<int> dp(v.size() + 1, 0);
dp[0] = 1;
for (int x : v)
{
for (int i = 0; i <= x; i++)
{
dp[x+1] += dp[i];
}
}
int result = 0;
for (int i = 0; i <= (int)v.size(); i++){
result += dp[i];
}
return result;
}
int isdiv(ll v) {
for(auto i : primos) {
while(v%i==0) v/=i;
}
return v==1;
}
vector<int> add(vector<int> a, vector<int> b) {
vector<int> ans;
for(auto v : a) ans.push_back(v+(int)b.size());
for(auto v : b) ans.push_back(v);
return ans;
}
vector<int> multiply(vector<int> a, vector<int> b) {
vector<int> ans;
for(auto v : a) ans.push_back(v);
for(auto v : b) ans.push_back(v+(int)a.size());
return ans;
}
vector<int> getdp(ll v) {
ll ov=v;
if(pans.find(v)!=pans.end()) return pans[v];
vector<int> ans(100);
ll diff=0;
while((int)ans.size()>90) {
while(!isdiv(v)) {
--v;
++diff;
}
ans=vector<int>();
ll prod=1;
ll val=v;
for(auto i : primos) {
while(val%i==0) {
val/=i;
prod*=i;
if(prod>=MAXV) {
prod/=i;
ans=multiply(ans, dp[prod]);
prod=i;
}
}
}
ans=multiply(ans, dp[prod]);
ans=add(ans, dp[diff+1]);
++diff;
--v;
//cout << v << " " << diff << " " << ans.size() << endl;
}
pans[ov]=ans;
return ans;
}
int primo(int v) {
for(int i=2;i*i<=v;i++) if(v%i==0) return 0;
return 1;
}
void init() {
if(initted) return;
initted=1;
cin.tie(nullptr);
ios::sync_with_stdio(false);
for(int i=0;i<MAXV;i++) dp[i]=vector<int>(100);
for(int n=0;n<=10;n++) {
vector<int> vec;
for(int i=0;i<n;i++) vec.push_back(i);
do {
int ct=count_increasing_b(vec);
if(ct>MAXV) continue;
if(n<(int)dp[ct].size()) dp[ct]=vec;
} while(next_permutation(vec.begin(), vec.end()));
}
auto start=chrono::high_resolution_clock::now();
for(int k=0;k<5;k++) {
for(int i=2;i<MAXV;i++) {
int l=min(i, 1024);
for(int j=1;j<l;j++) {
if((int)dp[j].size()+(int)dp[i-j+1].size()<(int)dp[i].size()) dp[i]=add(dp[j], dp[i-j+1]);
}
}
for(int i=2;i<MAXV;i++) {
for(int j=2, k=2*i;j<=i&&k<MAXV;j++,k+=i) {
if((int)dp[i].size()+(int)dp[j].size()<(int)dp[k].size()) dp[k]=multiply(dp[i], dp[j]);
}
}
}
for(int i=2;i<MAXV;i++) {
if(primo(i)) primos.push_back(i);
}
}
vector<int> construct_permutation(long long k) {
init();
return getdp(k);
}
