#include <bits/stdc++.h>
using namespace std;
/*
The judge provides this function.
Do NOT define it yourself in the real submission.
*/
pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
vector<long long> Q(N, 0); // final counts
vector<long long> Mmin(N, -1); // Mmin[i] = smallest M where type i appears
/*
Step 1: For each type i = 1 .. N-1,
binary search the smallest M such that type i appears.
*/
for (int i = 1; i < N; i++) {
long long low = 1;
long long high = P0 - 1;
long long ans = -1;
while (low <= high) {
long long mid = (low + high) / 2;
auto res = transaction(mid);
auto &L = res.first;
bool found = false;
for (int x : L) {
if (x == i) {
found = true;
break;
}
}
if (found) {
ans = mid;
high = mid - 1; // try smaller M
} else {
low = mid + 1; // need more coins
}
}
Mmin[i] = ans;
}
/*
Step 2: Use the discovered Mmin[i]
to buy exactly i souvenirs of type i
*/
for (int i = 1; i < N; i++) {
for (int k = 0; k < i; k++) {
auto res = transaction(Mmin[i]);
for (int x : res.first) {
Q[x]++;
}
}
}
/*
Step 3: Output final counts
*/
}
