#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.
//
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(int N, int K, long long A, int S) {
vector<int> a;
a.resize(N+1,0);
int l=1,r=N;
while(l<r){
int mid=(l+r)/2;
if(a[mid]==0){
a[mid]=skim(mid);
}
if(a[mid]>=A){
r=mid;
}
else{
l=mid+1;
}
}
if(l<K){
impossible();
return;
}
set<int> b;
b.insert(l);
if(a[l]==0){
a[l]=skim(l);
}
int sum=a[l];
for(int i=1;i<=K-1;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;
}
b.clear();
sum=0;
for(int i=l-K+1;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;
}
if(l==K){
impossible();
return;
}
b.clear();
sum=0;
for(int i=l-K;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;
}
impossible();
}
