#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#include "books.h"
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, long long A, int S) {
ll mins[K];
for(int i = 0; i < K; i++)
{
mins[i] = skim(i+1);
}
ll sum = 0;
for(int i = 0; i < K; i++)
sum += mins[i];
if(sum > A*2) {
impossible();
return;
}
if(sum >= A) {
vector<int> res;
for(int i = 0; i < K; i++)
res.push_back(i+1);
answer(res);
return;
}
// at this point, every element in mins is < 1, so lets find first where >= 1
int l = K, r = N;
while(l < r)
{
int m = (l+r) / 2;
ll x = skim(m+1);
if(x > A)
r = m;
else
l = m+1;
}
if(l < N)
{
ll big = skim(l+1);
sum = 0;
vector<int> res;
for(int i = 0; i < K-1; i++) {
sum += mins[i];
res.push_back(i+1);
}
sum += big;
res.push_back(l+1);
if(sum <= A*2)
{
answer(res);
return;
}
}
// now we need k maximums or some like that
vector<pair<int, ll> > fake_arr;
for(int i = 0; i < K; i++)
{
fake_arr.push_back(mp(i, mins[i]));
}
for(int i = max(l-K, K); i < l; i++)
{
fake_arr.push_back(mp(i, skim(i+1)));
}
int n = fake_arr.size();
// check that max is good
sum = 0;
for(int i = n-K; i < n; i++)
{
sum += fake_arr[i].se;
}
if(sum < A)
{
impossible();
}
// now min and max are good, ans somewhere in between
vector<int> res;
sum = 0;
for(int i = 0; i < K; i++)
{
sum += fake_arr[i].se;
res.push_back(i);
}
for(int i = K-1; i >= 0; i--)
{
int nx = (i == K-1) ? n : res[i+1];
while(res[i] < nx)
{
if(sum >= A && sum <= A*2)
{
for(int j = 0; j < K; j++)
{
res[j] = fake_arr[res[j]].fi+1;
}
answer(res);
return;
}
if(res[i]+1 >= nx)
break;
sum -= fake_arr[res[i]].se;
res[i]++;
sum += fake_arr[res[i]].se;
}
}
// literally impossible
assert(0);
}
/*
15 3 42 40
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/
