#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define inf 1ll<<60
#define rep(i,a,b) for (ll i=a;i<(b);i++)
#define MP make_pair
#define mod (ll)998244353
#define SZ(x) (int(x.size()))
#define ALL(x) x.begin(),x.end()
#define endl "\n"
ll lowbit(ll x) {return x&(-x);}
#include "souvenirs.h"
struct eqn{
vector<int>elem; ll sum;
eqn(vector<int>e, ll s): elem(e), sum(s){}
void clear(vector<ll>&P, ll bound){
while(elem.back()>bound){
sum-=P[elem.back()];
elem.pop_back();
}
}
};
eqn modified_transaction(ll m){
pair<vector<int>,ll> tmp = transaction(m);
return {tmp.fi,m-tmp.se}; //sum of all items brought
}
void buy_souvenirs(int N, long long P0) {
vector<ll>P(N,0),rem(N,0);
rep(i,1,N)rem[i]=i;
stack<eqn>s; //store the states
ll bound = N-1; //found P[i] for all i>bound
s.push({{0},P0});
while(bound){
eqn u=s.top();
u.clear(P,bound); //remove all confirmed P[i] from eqn
if(u.elem.size()==1 and u.elem[0]==bound){ //found a new P[bound]
s.pop();
P[bound]=u.sum;
bound--;
}else{
ll amt = (u.sum-1)/u.elem.size(); //only items with P < P max in the set could be brought
eqn next = modified_transaction(amt); //thus will repeat until we get P[bound]
for(auto x:next.elem)rem[x]--;
s.push(next);
}
}
rep(i,1,N)while(rem[i]--)transaction(P[i]);
return;
}
//max number of purchases is 4950 so 5000 is useless info
