typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
vector<int> construct_permutation(ll k){
k--;
vector<int>res;
int l=0,r=-1;
while(k){
if(k&1){
k>>=1;
res.pb(r--);
}
else{
k--;
res.pb(l++);
}
}
int n=res.size();
for(int &x:res){
if(x<0)x+=n;
}
reverse(res.begin(),res.end());
return res;
}
