#include "light.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct pair_hash{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
ll n;
vll curr = {};
void prepare(){
n = 1LL;
curr = {1LL};
}
ll getX(ll P){
if((n - P) & 1LL){
return (n - P) / 2LL;
}else{
return (n - P) / 2LL - 1;
}
}
//obie funkcje zwracają (p, ncurr)
pair<ll, vll> join(ll p){
n += p;
set<pll> intervals;
int i = 0;
while(i < sz(curr)){
int pocz = i;
while(i + 1 < sz(curr) && curr[i] + p >= curr[i + 1] - 1){
i++;
}
intervals.insert(mp(max(2LL, curr[pocz]), min(n, curr[i] + p)));
i++;
}
// cerr << "JOINING: " << p << '\n';
// cerr << n << '\n';
// debug(curr);
// for(auto ele : intervals){
// cerr << ele << '\n';
// }
vll ncurr = {1LL};
ll P = 1LL;
while(true){
ll x = getX(P);
// cerr << x << ' ' << P << '\n';
if(x <= 0LL){
break;
}
//musi być coś w przedziale [n - 2 * x, n - x]
auto it = intervals.lower_bound(mp((ll)n - x + 1, 0LL));
it--;
// cerr << (*it).fi << ' ' << (*it).se << '\n';
P = min((*it).se, n - x);
ncurr.pb(P);
}
if(ncurr.back() != n){
ncurr.pb(n);
}
curr = ncurr;
//debug(curr);
return mp(p, ncurr);
}
pair<ll, vll> leave(ll p){
n -= p;
set<pll> intervals;
int i = 0;
while(i < sz(curr)){
if(curr[i] > n){
break;
}
int pocz = i;
while(i + 1 < sz(curr) && curr[i] + p >= curr[i + 1] - 1){
i++;
}
intervals.insert(mp(max(2LL, curr[pocz]), min(n, curr[i] + p)));
//cerr << max(2LL, curr[pocz]) << ' ' << min(n, curr[i] + p) << '\n';
if(curr[i] + p > n){
break;
}
i++;
}
// cerr << "LEAVING: " << p << '\n';
// cerr << n << '\n';
// debug(curr);
// for(auto ele : intervals){
// cerr << ele << '\n';
// }
vll ncurr = {1LL};
ll P = 1LL;
while(true){
ll x = getX(P);
//cerr << x << ' ' << P << '\n';
if(x <= 0LL){
break;
}
//musi być coś w przedziale [n - 2 * x, n - x]
auto it = intervals.lower_bound(mp((ll)n - x + 1, 0LL));
it--;
P = (*it).se;
ncurr.pb(P);
}
if(ncurr.back() != n){
ncurr.pb(n);
}
curr = ncurr;
// debug(curr);
return mp(p, ncurr);
}
