#include "souvenirs.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 1000000007;
void processi(ll i, vector<ll> &P, vector<ll> &cnt);
void process(vector<int> seq, ll sum, vector<ll> &P, vector<ll> &cnt) {
/*for(auto & x : seq) cout << x << ' ';
cout << '\n';
cout << sum << '\n';*/
vector<int> v;
for(auto & x : seq) {
if(P[x] == -1) v.push_back(x);
else sum -= P[x];
}
ll k = v.size();
if(k == 0) return;
if(k == 1) {
P[v[0]] = sum;
return;
}
auto res = transaction(sum / k);
for(auto & x : res.F) cnt[x]++;
process(res.F, sum / k - res.S, P, cnt);
processi(v.back(), P, cnt);
process(v, sum, P, cnt);
}
void processi(ll i, vector<ll> &P, vector<ll> &cnt) {
if(P[i] != -1) return;
if(P[i-1] == -1) processi(i-1, P, cnt);
if(P[i] != -1) return;
auto res = transaction(P[i-1] - 1);
for(auto & x : res.F) cnt[x]++;
process(res.F, P[i-1] - 1 - res.S, P, cnt);
}
void buy_souvenirs(int N, long long P0) {
vector<ll> P(N,-1), cnt(N,0); P[0] = P0;
processi(N-1, P, cnt);
for(ll i=0; i<N; i++) for(ll j=cnt[i]; j<i; j++) transaction(P[i]);
return;
}
