#include "bits/stdc++.h"
#include "light.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
const ll inf = (1LL) << 62;
const ll L = 60;
ll n;
vector<ll> pos(L);
vector<ll> s(L);
vector<ll> pot(L+1);
ll sz(int k) {
if (pos[k] == inf) return 0;
return pot[k];
}
void prepare() {
debug(inf);
n = 1;
pot[0] = 1;
for (int i = 1; i <= L; ++i) pot[i] = pot[i-1] * 2;
for (int k = 0; k < L; ++k) {
pos[k] = 2LL - (pot[k+1] - 1);
}
debug(pos);
}
vector<ll> make() {
cerr << "make \n";
vector<ll> ret;
ll rest = 1;
for (int k = 0; k < L; ++k) {
s[k] = min(s[k], pot[k] - rest);
rest += sz(k);
}
for (int k = 0; k < L; ++k) {
if (pos[k] == inf) continue;
ll last = pos[k] + pot[k];
cerr << "adding from bucket " << k << '\n';
for (int l = 0; l <= k; ++l) {
if (pos[k] + s[k] >= last - pot[l] &&
last - pot[l] <= n && last - pot[l] >= 1) {
ret.eb(last - pot[l]);
cerr << "add " << last - pot[l] << endl;
}
}
if (pos[k] + s[k] >= 1 && s[k] <= pot[k] - 1 && pos[k] + s[k] <= n) {
cerr << "add " << pos[k] + s[k] << endl;
ret.eb(pos[k] + s[k]);
}
}
ret.eb(1);
sort(all(ret));
auto last = unique(all(ret));
ret.erase(last, ret.end());
return ret;
}
pair<ll, vector<ll>> join(ll p) {
n += p;
for (int k = 0; k < L; ++k)
if (pos[k] != inf) pos[k] += p;
return {p, make()};
}
ll fix_back(ll p) {
cerr << "fix back \n";
int k = 0;
ll c = 0;
while (c + sz(k) <= p) {
cerr << "deleting T(" << k << ") with size = " << sz(k) << endl;
c += sz(k);
pos[k] = inf;
s[k] = 0;
k++;
}
if (c == p) {
for (int l = k; l < L; ++l)
if (pos[l] != inf) s[l] = min(pot[l], s[l] + c);
return 0LL;
}
ll posk = pos[k];
for (int l = k-1; l >= 0; --l) {
pos[l] = posk;
posk += pot[l];
}
pos[k] = inf;
s[k] = 0;
for (int l = 0; l < L; ++l)
if (pos[l] != inf) s[l] = min(pot[l], s[l] + c + 1);
return p - c - 1;
}
pair<ll, vector<ll>> leave(ll p) {
ll t = p;
n -= p;
cerr << "leave " << p << endl;
while (p) {
p = fix_back(p);
}
for (int l = 0; l < L; ++l)
if (pos[l] != inf) pos[l] -= p;
return {t, make()};
}
