#include <bits/stdc++.h>
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using pill = pair<int, ll>;
using vpill = vector<pill>;
using plli = pair<ll, int>;
using vplli = vector<plli>;
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n)-1; i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a)-1; i >= (b); --i)
vint construct_basic(ll k) {
bitset<64> b(k);
int LOG = __lg(k);
vint arr(LOG); iota(all(arr), 0);
int arr_max = LOG-1;
rrep(i, LOG) if (b[i]) {
if (i == 0) arr.insert(arr.begin(), sz(arr));
else {
int pos = sz(arr)-i;
arr.insert(arr.begin(), arr[pos]);
FOR(j, pos+1, sz(arr)) arr[j]++;
}
}
return arr;
}
vint construct_permutation(ll k) {
vplli factors;
for (ll i = 2; i * i <= k; i++) {
int count = 0;
while (k % i == 0) {
k /= i, count++;
}
if (count) factors.push_back({i, count});
}
if (k > 1) factors.push_back({k, 1});
vint arr;
for (auto& [f, c]: factors) {
vint narr = construct_basic(f);
for (auto& nval: narr) nval += sz(arr);
while (c--) {
arr.insert(arr.end(), narr.begin(), narr.end());
for (auto& nval: narr) nval += sz(narr);
}
}
return arr;
}
