#include <bits/stdc++.h>
using namespace std;
const int N = 100;
long long ell[100] = {2660822841688, 1543875428686, 854806807668, 458519997429, 239172625298,
131829070422, 67618394369, 36652285201, 20851110356, 11296028942,
5745612859, 3007239918, 1815432867, 1111304349, 699498544, 388399115,
222002146, 142384930, 73211028, 40503786, 26228775, 13711027, 8154615,
4090858, 2686055, 1350405, 677104, 361883, 182963, 111440, 58780, 31043,
16035, 9703, 5634, 3002, 1624, 1040, 567, 367, 189, 112, 72, 39, 21,
11, 6, 4, 2, 1};
int n;
pair<vector<int>, long long> transaction(long long M);
/*
pair<vector<int>, long long> transaction(long long M)
{
vector<int> a;
for (int i = 0; i < n; ++i)
{
if (ell[i] <= M)
{
M -= ell[i];
a.push_back(i);
}
}
return pair<vector<int>, long long>(a, M);
}*/
struct el
{
vector<int> s;
long long b, r;
bool queried = 0;
};
vector<el> q;
long long value[N];
int number[N];
void update_data(el &r);
void check_to_remove(el r)
{
if (r.s.size() == 1)
{
value[r.s[0]] = r.b - r.r;
for (int i = 0; i < (int)q.size(); ++i)
update_data(q[i]);
}
}
void figure_smallest(el &va);
void update_data(el &r)
{
bool updated = false;
for (int i = 0; i < (int)r.s.size(); ++i)
{
if (value[r.s[i]])
{
r.b -= value[r.s[i]];
r.s.erase(r.s.begin() + i);
updated = true;
r.queried = 0;
--i;
}
}
check_to_remove(r);
// if (r.s.size() > 1 && updated)
//{
// figure_smallest(r);
// }
}
void do_q(long long a)
{
pair<vector<int>, long long> result = transaction(a);
el b;
b.s = result.first;
b.b = a;
b.r = result.second;
for (int i = 0; i < (int)b.s.size(); ++i)
{
number[b.s[i]]++;
}
update_data(b);
q.push_back(b);
}
void recheckAvg(long long &avg, long long num, el va)
{
bool any_good = false;
for (int i = va.s[0]; i < va.s[va.s.size() - 1] - 1; ++i)
{
if (value[i] != 0)
any_good = true;
if (value[i] != 0 && value[i + 1] == 0)
{
avg = value[i] - 1;
return;
}
}
if (any_good)
avg = 0;
}
void figure_smallest(el &va)
{
if (va.s.size() == 1)
{
check_to_remove(va);
return;
}
if (va.s.size() == 0)
return;
if (va.queried)
return;
va.queried = 1;
long long avg = (va.b - va.r) / (long long)va.s.size();
recheckAvg(avg, (long long)va.s.size(), va);
if (avg == 0)
return;
do_q(avg);
figure_smallest(q.back());
}
void finish_all()
{
for (int i = 0; i < n; ++i)
{
if (value[i] == 0)
{
while (1)
;
}
while (number[i] < i)
{
do_q(value[i]);
}
}
}
bool don()
{
for (int i = 0; i < n; ++i)
if (!value[i])
return false;
return true;
}
void buy_souvenirs(int nu, long long P0)
{
n = nu;
value[0] = P0;
while (!don())
{
for (int j = n - 2; j >= 0; --j)
{
if (number[j + 1] < j + 1 && value[j] != 0 && value[j + 1] == 0)
{
do_q(value[j] - 1);
break;
}
}
for (int i = q.size() - 1; i >= 0; --i)
{
check_to_remove(q[i]);
}
for (int i = q.size() - 1; i >= 0; --i)
{
if (q[i].s.size() == 0)
{
q.erase(q.begin() + i);
--i;
}
if (q[i].s.size() != 0 && !q[i].queried)
{
figure_smallest(q[i]);
}
}
}
/*
for (int j = 1; j < n; ++j)
{
if (value[j] == 0)
do_q(value[j - 1] - 1);
while (value[j] == 0)
{
for (int i = 0; i < (int)q.size(); ++i)
{
check_to_remove(q[i]);
if (q[i].s.size() != 0)
{
figure_smallest(q[i]);
}
}
}
q.clear();
}*/
finish_all();
}
/*
int main()
{
buy_souvenirs(50, 2660822841688);
cerr << "Result";
for (int i = 0; i < n; ++i)
cerr << number[i] << " ";
return 0;
}*/
