#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 sub5(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;
while(1){
cost/=2;
pair<vector<int>, long long> res=ask(cost,rem);
if(res.first.size()==1 && res.first[0]==N-2){
cost-=1+res.second;
cost*=2;
}
if(res.first[0]==N-1){
cost-=res.second;
costs.back()=cost;
break;
}
}
for(int i=N-2;rem[i];i--){
cost*=2;
pair<vector<int>, long long> res=ask(cost,rem);
for(auto x:res.first)cost-=costs[x];
cost-=res.second;
costs[i]=cost;
}
for(int i=0;i<N;i++){
while(rem[i]>0){
rem[i]--;
transaction(costs[i]);
}
}/*
for(int i=0;i<N;i++){
cout<<costs[i]<<" ";
}
cout<<endl;*/
}
void buy_souvenirs(int N, long long P0) {
if(N==3)sub4(N,P0);
else if(N==2) sub1(N,P0);
else sub5(N,P0);
return;
}
