#include "souvenirs.h"
#include <utility>
#include <vector>
using namespace std;
#include<bits/stdc++.h>
typedef long long ll;
#define rep(i,a,b) for(int i = a; i < b; i++)
void buy_souvenirs(int N, long long P0) {
if (N == 2) {
pair<vector<int>, ll> res = transaction(P0-1);
return;
}
if (N == 3) {
pair<vector<int>, ll> res = transaction(P0-1);
if (res.first.size() == 2) {
ll remain = res.second;
ll used = P0-1-remain;
res = transaction(used/2);
}
else {
ll A = P0-1 - res.second;
res = transaction(A-1);
res = transaction(A-1);
}
return;
}
int n = N;
vector<int> q_cnt(n, 0);
vector<int> here;
ll sum;
ll remainder;
auto q = [&](ll price) {
pair<vector<int>, ll> res = transaction(price);
here = res.first;
remainder = res.second;
sum = price - remainder;
for (auto x : here) q_cnt[x]++;
};
vector<int> has(n, 0);
vector<set<int>> obj(n);
vector<ll> s(n,0);
vector<ll> val(n, -1);
ll p = P0-1;
while (!(here.size() == 1 && here[0] == N-1)) {
q(p);
if (here.size() == 1) p = sum-1;
else p = sum / here.size();
has[here[0]] = 1;
for (auto x : here) obj[here[0]].insert(x);
s[here[0]] = sum;
}
val[n-1] = s[n-1];
auto clear = [&](int x) {
rep(i,0,x) {
if (obj[i].find(x) != obj[i].end()) {
obj[i].erase(x);
s[i] -= val[x];
}
}
};
clear(n-1);
int un_finished = n-2;
int iter = 0;
while (un_finished && iter++ < 1000) {
for (int i = n-2; i >= 0; i--) {
if (val[i] != -1 && val[i+1] != -1) continue;
if (val[i] == -1 && obj[i].size() == 1) {
val[i] = s[i];
clear(i);
un_finished--;
break;
}
if (val[i] != -1 && has[i+1] == 0) {
q(val[i]-1);
has[here[0]] = 1;
for (auto x : here) obj[here[0]].insert(x);
s[here[0]] = sum;
for (auto x : here) if (val[x] != -1) {
s[here[0]] -= val[x];
obj[here[0]].erase(x);
}
break;
}
if (has[i] && val[i] == -1) {
ll p = s[i] / obj[i].size();
q(p);
has[here[0]] = 1;
for (auto x : here) obj[here[0]].insert(x);
s[here[0]] = sum;
for (auto x : here) if (val[x] != -1) {
s[here[0]] -= val[x];
obj[here[0]].erase(x);
}
break;
}
}
}
rep(i,0,n) while (q_cnt[i] < i) q(val[i]);
//rep(i,0,n) cout << val[i] << " "; cout << endl;
}
// sum(S) = a, P[-1] > b
// next query : a/size(S)?
// x + y + z = s, x > y > z
// consider Q[i] = P[i] + i, then Q[0] >= Q[1] >= ...
