#include <bits/stdc++.h>
#include "books.h"
#define ll long long
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this 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)
{
int l = -1;
int r = N;
ll lb = 1e18;
while (l + 1 < r)
{
int m = (l + r) / 2;
ll v = skim(m + 1);
if (v >= A) { r = m; lb = min(lb, v); }
else l = m;
}
vector<int> qs;
for (int i = 0; i < K; i++) qs.push_back(i);
for (int i = 0; i < K && l - i >= 0; i++) qs.push_back(l - i);
sort(qs.begin(), qs.end());
qs.erase(unique(qs.begin(), qs.end()), qs.end());
int m = qs.size();
vector<ll> vs(m);
for (int i = 0; i < m; i++) vs[i] = skim(qs[i] + 1);
for (int i = 0; i < K - 1; i++) lb += vs[i];
if (A <= lb && lb <= 2*A)
{
vector<int> res(K);
iota(res.begin(), res.end(), 1);
res[K - 1] = r + 1;
if (res[K - 1] > res[K - 2])
{
answer(res);
return;
}
}
ll cr = 0;
vector<signed> taken;
for (int i = 0; i < K; i++)
{
taken.push_back(qs[i] + 1);
cr += vs[i];
}
auto check = [&](ll v, vector<int> ind)
{
if (v < A || 2*A < v) return false;
vector<int> res(ind.end() - K, ind.end());
answer(res);
return true;
};
if (check(cr, taken)) return;
for (int i = K; i < m; i++)
{
cr -= vs[i - K];
cr += vs[i];
taken.push_back(qs[i] + 1);
if (check(cr, taken)) return;
}
impossible();
}
