#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
struct Entry {
pair<vector<int>, long long> ans;
int count;
long long price;
};
void buy_souvenirs(int N, long long P0) {
// std::pair<std::vector<int>, long long> res = transaction(3);
vector<long long> res(N);
vector<int> curr(N);
res[0] = P0;
int cnt = 1;
stack<Entry> st;
long long price = res[0]-1;
while (cnt < N) {
cout << price << endl;
pair<vector<int>, long long> ans = transaction(price);
int count = ans.first.size();
for (int i = 0; i < N; i++) {
curr[ans.first[i]]++;
}
if (count == 1) {
res[ans.first[0]] = price - ans.second;
cnt++;
bool down = false;
for (int i = ans.first[0]+1; i < N; i++) down |= res[ans.first[0]] == 0;
if (down) price = res[ans.first[0]]-1;
else {
bool found = false;
while (st.size() && !found) {
Entry entry = st.top(); st.pop();
int tmpCount = 0, tmpSum = 0;
for (int i = 0; i < N; i++) {
if (entry.ans.first[i] == 0) continue;
if (res[i] != 0) {
tmpSum += res[i];
continue;
}
tmpCount++;
}
if (tmpCount == 1) {
for (int i = 0; i < N; i++) {
if (res[entry.ans.first[i]] == 0) continue;
res[entry.ans.first[i]] = entry.price-entry.ans.second-tmpSum;
cnt++;
}
}
long long tmpPrice = entry.price-entry.ans.second;
for (int i = N-1; i >= 0; i--) {
if (res[entry.ans.first[i]] == 0) break;
tmpPrice -= res[entry.ans.first[i]];
}
if (tmpPrice != 0) {
price = tmpPrice;
found = true;
}
}
if (!found) {
for (int i = N-2; i >= 0; i--) {
if (res[i+1] == 0 && res[i] != 0) {
price = res[i]-1;
break;
}
}
}
}
} else {
st.push({ans, count, price});
price = (price - ans.second)/count;
}
// cout << res[0] << " " << res[1] << " " << res[2] << endl;
}
for (int i = 0; i < N; i++) {
while (curr[i] < i) {
curr[i]++;
transaction(res[i]);
}
}
return;
}
