#include <vector>
#include <iostream>
#include <algorithm>
#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) {
vector<int> lowest(K);
int losum = 0;
for(int i = 0; i < K; i ++)
{
lowest[i] = skim(i + 1);
losum += lowest[i];
}
vector<int> ansvec(K);
for(int i = 0; i < K; i ++) ansvec[i] = i + 1;
if(losum > 2 * A) impossible();
else if(losum >= A) answer(ansvec);
int lo = 0, hi = N;
while(lo + 1 < hi)
{
int m = (lo + hi) / 2;
if(skim(m + 1) < A) lo = m;
else hi = m;
}
if(hi < N && losum - lowest[K - 1] + skim(hi + 1) < 2 * A)
{
ansvec[K - 1] = hi + 1;
answer(ansvec);
}
hi --;
if(hi < K) impossible();
int j = 0;
while(losum < A && hi > j)
{
losum += skim(hi + 1) - lowest[j];
ansvec[j] = hi + 1;
j ++;
hi --;
}
if(losum < A) impossible();
else answer(ansvec);
}
