#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
int n, ans[105], num[105];
bool visited[105];
void solve(vector<int> idx, int sum)
{
for(int i : idx) num[i]++;
int u = idx[0];
if(visited[u] == 1) return;
if(u == n-1){visited[u] = 1; ans[u] = sum; return;}
/*Now actually solve the problem*/
while(visited[idx.back()] == 1){
sum -= ans[idx.back()]; idx.pop_back();
}
while(idx.size() > 1){
long long ques = sum / idx.size();
pair<vector<int>, long long> a = transaction(ques);
solve(a.first, ques - a.second);
while(visited[idx.back()] == 1){
sum -= ans[idx.back()]; idx.pop_back();
}
}
visited[u] = 1; ans[u] = sum;
for(int i = u+1; i < n; i++) if(visited[i] == 0){
//Solve for all number after it
pair<vector<int>, long long> a = transaction(ans[i-1]-1);
solve(a.first, ans[i-1]-1 - a.second);
break;
}
}
void buy_souvenirs(int nn, long long P0) {
n = nn;
memset(ans, 0, sizeof(ans));
memset(num, 0, sizeof(num));
pair<vector<int>, long long> a = transaction(P0 - 1);
solve(a.first, P0 - 1 - a.second);
//We found all the values, now we finish everything
for(int i = 1; i < n; i++) while(num[i]++ < i) transaction(ans[i]);
}
