#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void sub1(int N, long long P0) {
pair<vector<int>, long long> res = transaction(P0-1);
}
void sub2(int N, ll P0){
for(int i=N-1;i>0;i--){
for(int j=N;j>i;j--){
transaction(i);
}
}
}
void sub3(int N,ll P0){
vector<ll> rem(N);
for(int i=0;i<N;i++){
rem[i]=i;
}
ll cost=P0-1;
for(int i=1;i<N;i++){
pair<vector<int>, long long> res =transaction(cost);
for(auto x:res.first)rem[x]--;
if(res.first.size()>1||res.second)cost--;
while(rem[i]){
res=transaction(cost);
for(auto x:res.first)rem[x]--;
}
cost--;
}
}
void sub4(int N, long long P0) {
pair<vector<int>, long long> res = transaction(P0-1);
ll cost=P0-1-res.second;
//cout<<"#"<<cost<<endl;
if(res.first.size()>1)
transaction(cost/2);
else{
transaction(cost-1);
transaction(cost-1);
}
}
pair<vector<int>, long long> ask(ll cost,vector<ll> &v){
pair<vector<int>, long long> res = transaction(cost);
for(auto x:res.first)v[x]--;
return res;
}
void full(int N,ll P0){
vector<ll> rem(N);
for(int i=0;i<N;i++){
rem[i]=i;
}
vector<ll> costs(N,0);
costs[0]=P0;
pair<vector<int>, long long> res;
ll cost=P0;
vector<pair<vector<int>, long long>> pre;
map<ll,ll> vis;
while(1){
cost--;
pair<vector<int>, long long> res=ask(cost,rem);
pre.push_back(res);
vis[res.first[0]]=pre.size();
pre.back().second=cost-res.second;
cost=cost-res.second;
if(res.first[0]==N-1){
costs.back()=cost;
break;
}
if(res.first.size()==1){
continue;
}else{
cost+=res.first.size()-1;
cost/=res.first.size();
}
}
for(int i=N-2;i>0;i--){
if(vis[i]){
pair<vector<int>, long long> res=pre[vis[i]-1];
cost=res.second;
for(auto x:res.first)cost-=costs[x];
costs[i]=cost;
continue;
}
ll nex=i-1;
while(!vis[nex]){
nex--;
}
pair<vector<int>, long long> res=pre[vis[i]-1];
cost=res.second;
ll cou=res.second;
for(auto x:res.first){
if(costs[x])cou--;
cost-=costs[x];
}
cost+=cou-1;
cost/=cou;
cost--;
res=ask(cost,rem);
pre.push_back(res);
vis[res.first[0]]=pre.size();
pre.back().second=cost-res.second;
i++;
continue;
}
for(int i=0;i<N;i++){
while(rem[i]>0){
rem[i]--;
transaction(costs[i]);
}
}
}
void buy_souvenirs(int N, long long P0) {
full(N,P0);
}
