#include <bits/stdc++.h>
#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) {
// TODO implement this function
vector <int> a(N+1,0);
int s1=0,s2=0;
for(int i=1; i<=K; i++) a[i]=skim(i),s1+=a[i];
for(int i=N; i>=N-K+1; i--) a[i]=skim(i);
if(s1>2*A || s2<A){
impossible();
return;
}
if(s1>=A){
vector <int> cur;
for(int i=1; i<=K; i++) cur.push_back(i);
answer(cur);
return;
}
if(s1>=A){
vector <int> cur;
for(int i=1; i<=K; i++) cur.push_back(i);
answer(cur);
return;
}
if(s2<=2*A){
vector <int> cur;
for(int i=N-K+1; i<=N; i++) cur.push_back(i);
answer(cur);
return;
}
s1-=a[K];
int l=K+1,r=N-K;
while(l<=r){
int mid=(l+r)>>1;
int v=skim(mid);
if(s1+v>=A and s1+v<=A+A){
vector <int> cur;
for(int i=1; i<K; i++) cur.push_back(i);
cur.push_back(mid);
answer(cur);
}else if(s1+v<A){
l=mid+1;
}else{
r=mid-1;
}
}
}
