#include <iostream>
#include <vector>
#define int long long
//#define TEST 1
using namespace std;
pair<vector<int32_t>, long long> transaction(long long m);
void buy_souvenirs(int32_t n, long long p0) {
if (n <= 3) {
auto x = transaction(p0 - 1);
if (n == 2) return;
if(x.first.size() == 1)
transaction((p0 - 2 - x.second)),
transaction((p0 - 2 - x.second));
else transaction((p0 - 1 - x.second) / 2);
return;
}
int p = p0, o = n - 1;
for (int i = 1; i < n; ++i) {
if ((i == (n - 1)) && (o != i)) {
for (int j = 0; j < o; ++j) transaction(1);
break;
}
auto x = transaction(p - 1);
int v = p - 1;
if ((x.second) || (x.first.size() > 1))
--v, --o;
for (int j = 1; j < i; ++j) transaction(v);
p = v;
}
}
#ifdef TEST
vector<int> p = {99, 97, 95, 93, 91, 89, 87, 85, 83, 81, 79, 77, 75, 73, 71, 69, 67, 65, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3};
pair<vector<int32_t>, long long> transaction(long long m) {
cout << m << ": ";
vector<int32_t> v;
for (int i = 0; i < p.size(); ++i)
if (p[i] <= m) {
cout << i << " ";
m -= p[i];
v.push_back(i);
}
cout << "rem: " << m << endl;
return { v, m };
}
int32_t main() {
buy_souvenirs(p.size(), p[0]);
}
#endif
