#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;
if (!m[mid])
m[mid] = skim(mid);
if (m[mid] > A)
r = mid;
else
l = mid + 1;
}
int t = l;
vector<ll> lp(K + 1);
for (int i = 1; i <= K; i++)
{
if (!m[i])
m[i] = skim(i);
lp[i] = lp[i - 1] + m[i];
}
if (t <= N)
{
if (!m[t])
m[t] = skim(t);
ll tot = lp[K - 1] + m[t];
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> rs(K + 1);
for (int i = 1; i <= K; i++)
{
if (!m[t - i])
m[t - i] = skim(t - i);
rs[i] = rs[i - 1] + m[t - 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();
}
