#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#define Ilveyuki ios::sync_with_stdio(false); cin.tie(nullptr);
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
//
// --- Sample implementation for the task books ---
//
// To compile trs program with the sample grader, place:
// books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
void solve(int N, int K, ll A, int S)
{
map<int, ll> m;
int l = 1, r = N + 1;
while (l < r)
{
int mid = l + (r - l) / 2;
ll v;
auto it = m.find(mid);
if (it == m.end())
{
v = skim(mid);
m[mid] = v;
}
else
v = it -> second;
if (v > A)
r = mid;
else
l = mid + 1;
}
int t = l;
vector<ll> lv;
for (int i = 1; i <= K; i++)
{
ll v;
auto it = m.find(i);
if (it == m.end())
{
v = skim(i);
m[i] = v;
}
else
v = it -> second;
lv.push_back(v);
}
vector<ll> lp(K + 1);
for (int i = 1; i <= K; i++)
{
lp[i] = lp[i - 1] + lv[i - 1];
}
if (t <= N)
{
ll xt;
auto it = m.find(t);
if (it == m.end())
{
xt = skim(t);
m[t] = xt;
}
else
xt = it -> second;
ll tot = lp[K - 1] + xt;
if (A <= tot && tot <= 2 * A)
{
vector<int> res;
for (int i = 1; i <= K - 1; i++)
{
res.push_back(i);
}
res.push_back(t);
answer(res);
return;
}
}
if (t - 1 < K)
{
impossible();
return;
}
vector<ll> rv;
int ss = t - K;
for (int i = ss; i <= t - 1; i++)
{
ll v;
auto it = m.find(i);
if (it == m.end())
{
v = skim(i);
m[i] = v;
}
else
v = it -> second;
rv.push_back(v);
}
vector<ll> rs(K + 1);
for (int i = 1; i <= K; i++)
{
rs[i] = rs[i - 1] + rv[K - i];
}
for (int i = 0; i <= K; i++)
{
ll tot = lp[K - i] + rs[i];
if (A <= tot && tot <= 2 * A)
{
vector<int> res;
for (int j = 1; j <= K - i; j++)
{
res.push_back(j);
}
for (int j = t - i; j <= t - 1; j++)
{
res.push_back(j);
}
answer(res);
return;
}
}
impossible();
}
