#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
typedef long long ll;
const int N = 100;
void print(ll x, char sep){
cout << x << sep;
}
ll check(ll x){
ll f[100] = {};
f[0] = 1, f[1] = 2;
if(f[1] > x) return 1;
for(int i = 2; i < 100; i++){
f[i] = f[i - 1] + f[i - 2];
if(f[i] + f[i - 1] > x) return i + 1;
}
return 0;
}
void buy_souvenirs(int n, ll p0) {
if(n == 3){
pair < vector < int >, ll > res;
res = transaction(p0 - 1);
if(res.first.size() == 1){
ll p1 = p0 - 1 - res.second;
transaction(p1 - 1);
transaction(p1 - 1);
return;
}
ll s = p0 - 1 - res.second;
transaction(s / 2);
return;
}
ll mx[N] = {}, mn[N] = {}, c[N] = {};
mx[0] = mn[0] = p0;
for(int i = 0; i + 3 < n; i++){
ll l, r;
while(c[i + 1] < i + 1){
pair < vector < int >, ll > v = transaction(mn[i] - 1);
for(int pos : v.first) c[pos]++;
}
l = 0, r = mx[i];
while(r - l > 1){
ll m = (l + r) / 2;
if(m + (m + 1) / 2 <= mx[i]) l = m;
else r = m;
}
mx[i + 1] = l;
l = 0, r = mx[i + 1];
while(r - l > 1){
ll m = (l + r) / 2;
if(check(m) >= n - i - 1 && m * 2 >= mn[i]) r = m;
else l = m;
}
mn[i + 1] = r;
}
pair < vector < int >, ll > v = transaction(mn[n - 3] - 1);
for(int pos : v.first) c[pos]++;
if(v.first.size() == 1){
if(v.first[0] == n - 2){
mn[n - 2] = mn[n - 3] - 1 - v.second;
while(c[n - 2] < n - 2) transaction(mn[n - 2]), c[n - 2]++;
while(c[n - 1] < n - 1) transaction(mn[n - 2] - 1), c[n - 1]++;
}
else{
mn[n - 1] = mn[n - 3] - 1 - v.second;
while(c[n - 2] < n - 2) transaction(mn[n - 1] * 2), c[n - 2]++;
while(c[n - 1] < n - 1) transaction(mn[n - 1]), c[n - 1]++;
}
}
else{
ll sum = mn[n - 3] - 1 - v.second;
while(c[n - 2] < n - 2) transaction(sum - 1), c[n - 2]++;
while(c[n - 1] < n - 1) transaction(sum / 2), c[n - 1]++;
}
}
