#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
#include "perm.h"
map<long long,vector<int>> cache;
vector<int> f(long long x){
if(x==1) return {};
if(cache.count(x)) return cache[x];
if(x%2==0){
vector<int> u = f(x/2);
u.push_back(sz(u));
return cache[x]=u;
}
vector<int> res = f(x/2);
for(int i=0;i<sz(res);i++) res[i]++;
res.push_back(sz(res)+1);
res.push_back(0);
for(int val : {3,5,7}){
if(x%val) continue;
vector<int> cur = f(x/val);
if(sz(cur)+val-1<sz(res)){
res=cur;
cur.clear();
int p=sz(res)+val-2;
for(int j=1;j<val;j++) res.push_back(p--);
}
}
return cache[x]=res;
}
vector<int> construct_permutation(long long k){
return f(k);
}
/*void _(){
int k;
cin >> k;
vector<int> ans = f(k);
cout << sz(ans) << '\n';
for(int x:ans) cout << x << ' ';
cout << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
