#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#include "perm.h"
vector<int> construct_permutation(long long k){
vector<int> ans;
int c = 0;
for(ll i = 0; i < __lg(k); i++){
ans.pb(c++);
}
int pos = ans.size() - 1;
for(ll i = __lg(k) - 1; i >= 0; i--){
if(k & (1LL << i)){
ans.insert(ans.begin() + pos, c++);
}
pos--;
}
return ans;
}
