#include<bits/stdc++.h> using namespace std; pair<vector<int>,long long> transaction(long long M); int cnt=0; pair<vector<int>,long long>c[105]; long long k[105]; long long p1[105]; int let[105]; void remove(vector<int>v) { for(int i:v) { let[i]--; } } void buy_souvenirs(int N,long long p0) { for(int i=0;i<N;i++) { let[i]=i; } long long last=p0-1; while(true) { auto [v,r]=transaction(last); remove(v); c[v[0]]={v,r}; k[v[0]]=last; long long sum=last-r; if(v.size()==1&&v.back()==N-1) { p1[N-1]=sum; break; } if(v.size()==1) { last=sum-1; } else { last=sum/long(v.size()); } } for(int i=N-2;i>=2;i--) { vector<int>v; long long r; long long next; if(c[i].first.empty()) { pair<vector<int>,long long>e=transaction(2*p1[i+1]); v=e.first,r=e.second; remove(v); next=2*p1[i+1]; } else { pair<vector<int>,long long>e=c[i]; v=e.first,r=e.second; next=k[i]; } p1[i]=next-r; for(int j=1;j<v.size();j++) { p1[i]-=p1[v[j]]; } } for(int i=2;i<N;i++) { for(int j=0;j<let[i];j++) { transaction(p1[i]); } } }