#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
bool test = false;
void buy_souvenirs(int N, long long P0) {
vector<long long> P(N),C(N);
P.at(0) = P0;
long long check = P0-1;
vector<bool> already(N); already.at(1) = true;
vector<pair<vector<int>,long long>> result;
while(true){
if(test) cout << check << endl;
pair<vector<int>,long long> buy = transaction(check);
auto &[B,coin] = buy;
if(test){
cout << "buy:";
for(auto b : B) cout << b << " ";
cout << " " << coin << endl;
}
coin = check-coin;
for(auto pos : B) C.at(pos)++;
int siz = B.size();
vector<bool> del(siz);
for(int i=0; i<siz; i++) if(P.at(B.at(i)) != 0) coin -= P.at(B.at(i)),del.at(i) = true;
{
vector<int> B2;
for(int i=0; i<siz; i++) if(!del.at(i)) B2.push_back(B.at(i));
siz = B2.size(); swap(B,B2);
}
assert(siz > 0);
if(siz == 1){
P.at(B.at(0)) = coin;
while(true){
vector<int> era;
for(int i=0; i<(int)result.size(); i++){
auto &[B2,left] = result.at(i);
for(int k=B2.size(); k--;) if(P.at(B2.at(k)) != 0){
left -= P.at(B2.at(k));
B2.erase(B2.begin()+k);
}
if(B2.size() == 1){
P.at(B2.at(0)) = left;
era.push_back(i);
}
else if(B2.size() == 0) era.push_back(i);
}
if(era.size() == 0) break;
reverse(era.begin(),era.end());
for(auto pos : era) result.erase(result.begin()+pos);
}
check = 0;
if(test){for(int i=0; i<N; i++) cout << P.at(i) << " "; cout << endl;}
if(test){for(int i=0; i<N; i++) cout << C.at(i) << " "; cout << endl;}
for(int i=N-1; i>0; i--) if(P.at(i) == 0 && P.at(i-1) != 0 && !already.at(i)){
already.at(i) = true;
check = P.at(i-1)-1;
break;
}
if(check == 0){
for(auto [C,left] : result){
int minc = *min_element(C.begin(),C.end());
int maxc = *max_element(C.begin(),C.end());
int n = C.size();
bool ng = false;
for(int i=minc; i<=maxc; i++) if(P.at(i) != 0){ng = true; break;}
if(ng) continue;
check = left/n;
}
if(result.size() == 0) break;
}
assert(check != 0);
}
else{
check = coin/siz;
result.emplace_back(buy);
}
}
for(int i=0; i<N; i++) while(C.at(i) < i){
if(test) cout << P.at(i) << endl;
transaction(P.at(i)),C.at(i)++;
}
}
