#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<vector<int>,ll> pvl;
ll n,val[105],cnt[105];
// find all the items that has value at most s by buying the most expensive item that less than s (v[0]) only once
void solve(ll s) {
pvl res=transaction(s);
s-=res.second;
vector<int> v=res.first;
for (auto s : v) ++cnt[s];
while (1) {
for (int i=(int)(v.size()-1); i>=0; --i) {
if (val[v[i]]!=-1) s-=val[v[i]], v.pop_back();
else if (i) {
solve(s/((int)(v.size())));
break;
} else {
val[v[0]]=s;
cout<<v[0]<<" "<<s<<"\n";
if (v[0]!=n-1) solve(val[v[0]]-1);
return;
}
}
if (v.size()==0) break;
}
}
void buy_souvenirs(int N, ll P0) {
n=N;
memset(val,-1,sizeof(val));
solve(P0-1);
for (int i=0; i<n; ++i) {
for (int j=0; j<i-cnt[i]; ++j) transaction(val[i]);
}
}
