#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
std::vector<int> construct_permutation(long long k) {
vector<ll> extra;
long long sum = 0;
if(k == 2){
return {0};
}
vector<int> p;
long long ts = 0;
for(ll d = min(k - 1, (long long)1e6); d >= 3; d--){
while(k % d == 0){
k /= d;
extra.pb(d - 1);
}
}
if(k == 2){
ll hi = extra.back();
extra.pop_back();
extra.pb((hi + 1) * k - 1);
}else{
extra.pb(k - 1);
}
long long hi = 0;
for(ll d : extra){
int tmp = d;
vector<int> bits;
long long s = 0;
while(d > 0){
for(int i = 63 ; i >= 1; i--){
if((1ll << i) - 1 <= d){
bits.pb(i);
d -= (1ll << i) - 1;
s += i;
break;
}
}
}
s--;
for(int i : bits){
int cnt = s - i + 1;
for(int j = cnt; j <= s; j++) p.pb(hi + j);
assert(hi + s <= 1e6);
s -= i;
}
hi = p.size();
}
return p;
}
