#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) {
vector<int> a;
a.resize(N+1,0);
int l=1,r=N;
int h=A/K+(A%K!=0);
while(l<r){
int mid=(l+r)/2;
if(a[mid]==0){
a[mid]=skim(mid);
}
if(a[mid]>=h){
r=mid;
}
else{
l=mid+1;
}
}
int l1=max(l-K+1,1);
l=l1+K-1;
int sum=0;
set<int> b;
for(int i=l1;i<=l;i++){
if(a[i]==0){
a[i]=skim(i);
}
sum+=a[i];
b.insert(i);
}
if(sum>=A && sum<=2*A){
vector<int> res;
for(auto x:b){
res.push_back(x);
}
answer(res);
return;
}
for(int i=l+1;i<=min(l+K,N);i++){
sum+=a[i];
sum-=a[i-K];
b.erase(i-K);
b.insert(i);
if(sum>=A && sum<=2*A){
vector<int> res;
for(auto x:b){
res.push_back(x);
}
answer(res);
return;
}
}
impossible();
}
