#include <bits/stdc++.h>
#include "perm.h"
#define ll long long
#define ull unsigned long long
#define pb push_back
#define sln cout << "\n";
#define sz(x) (int)(x.size())
#define s second
#define ld long double
#define f first
#define pt complex <ld>
#define cyes cout << "YES\n";
#define cno cout << "NO\n";
#define bitcount __builtin_popcountll
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#pragma comment (linker, "/stack:200000")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unswitch-loops")
#pragma GCC target ("avx2")
//#pragma GCC optimize("O3, unroll-loops, Ofast")
//#pragma GCC target("avx, avx2, fma")
//#pragma GCC optimize("no-exceptions")
//#pragma GCC optimize("no-rtti")
//#pragma GCC optimize("stack-reuse=all")
//#define int ll //__int128_t
#define lll __int128_t
using namespace std;
const ll mod = 1e9 + 7;
ld pi = acos(-1);
ll inf = (ll)1e18;
ll binpow (ll n, ll s) {
n %= mod;
ll t = n;
ll ans = 1LL;
while (s > 0LL) {
if ((s & 1)) {
ans = (ans * t) % mod;
}
t = (t * t) % mod;
s = (s >> 1LL);
}
return ans;
}
int lg (ll n) {
return 63 - __builtin_clzll(n);
}
ll lcm (ll a, ll b) {
return (a * b / __gcd (a, b));
}
vector <int> construct_permutation(ll k) {
vector <int> a;
for (int i = 0; i < lg (k); i ++) a.pb (i);
k -= (1LL << lg(k));
for (int i = 60; i >= 0; i --) {
if ((1LL << i) <= k) {
k -= (1LL << i);
a.insert (a.begin() + i, sz(a));
}
}
return a;
}
/*
()(())
(())()()
g++ grader.cpp problem.cpp -o program.exe -std=c++17
program.exe
-1 1 -1 -1 1 -1
-1 1 -1 1 -1 1 -1 -1
0 1 2 3 4
32
0 1 2 3 4
0 1 2 4 3
0 1 4 2 3
1 0 0 1 0 0 1 0
6 4
1 2 4 3 5 6
1 2 3 4 5 6
((()))()()
*/
