#include <bits/stdc++.h>
#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;
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 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
pair<vector<int>, long long> transaction(long long m){
cout << m << ": ";
vector<int> 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
