#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<pair<int,long long> > smol,beeg;
long long ts=0,tb=0;
for(int i=1; i<=K; i++){
smol.push_back({i,skim(i)});
ts+=smol.back().second;
}
vector<int> ans;
if(ts>2ll*A){
impossible();
return;
}
else if(ts>=A){
for(int i=1; i<=K; i++) ans.push_back(i);
answer(ans);
return;
}
int lo=1,hi=N+1,mid;
while(lo<hi){
mid=(lo+hi)/2;
long long x=skim(mid);
if(x<A) lo=mid+1;
else hi=mid;
}
long long more=2e17;
if(lo!=N+1) more=skim(lo);
if(more+ts-smol.back().second<=2ll*A){
for(int i=1; i<K; i++) ans.push_back(i);
ans.push_back(lo);
answer(ans);
return;
}
for(int i=K; i>0; i--){
beeg.push_back({lo-i,skim(lo-i)});
tb+=beeg.back().second;
}
if(tb<A){
impossible();
return;
}
else if(tb<=2ll*A){
for(int i=1; i<=K; i++) ans.push_back(lo-i);
answer(ans);
return;
}
for(int i=0; i<K; i++){
tb-=beeg[i].second;
tb+=smol[i].second;
if(A<=tb&&tb<=2ll*A){
for(int j=0; j<=i; j++) ans.push_back(smol[j].first);
for(int j=i+1; j<K; j++) ans.push_back(beeg[j].first);
answer(ans);
return;
}
}
assert(false);
}
