#include <bits/stdc++.h>
#include "books.h"
#define f first
#define s second
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) {
int hi=N,lo=1,m;
int ans=N+1;
vector<long long> val(N+1, -1);
//~ for(int i=1;i<=N;i++){
//~ val[i]=skim(i);
//~ }
//~ ans=lower_bound(val.begin(),val.end(),A)-val.begin();
//~ for(int i=1;i<=N;i++){
//~ for(int j=i+1;j<=N;j++){
//~ for(int k=j+1;k<=N;k++){
//~ long long cur = val[i]+val[j]+val[k];
//~ if(cur<=2*A and cur>=A){
//~ answer({i,j,k});
//~ return;
//~ }
//~ }
//~ }
//~ }
//~ impossible();
while(lo<=hi){
m=(lo+hi)/2;
val[m]=skim(m);
if(val[m]>=A){
ans=m;
hi=m-1;
}
else{
lo=m+1;
}
}
if(ans<k){
impossible();
return;
}
if(true){
vector<int> out;
long long sm=0;
for(int i=1;i<=k-1;i++){
sm+=(val[i]==-1? skim(i) : val[i]);
out.push_back(i);
}
out.push_back(ans);
sm+=(val[ans]==-1? skim(ans) : val[ans]);
if(sm>=A and sm <= 2*A){
answer(out);
return;
}
else if (ans==k){
impossible();
return;
}
}
vector<pair<long long,int>> pref, suff;
for(int i=1;i<=k;i++){
pref.push_back({(val[i]==-1? skim(i) : val[i]),i});
}
for(int i=ans-1;i>=ans-k;i--){
suff.push_back({(val[i]==-1? skim(i) : val[i]),i});
}
for(int i=0;i<=k;i++){
long long check2=0;
vector<int> out;
for(int j=0;j<i;j++){
check2+=pref[j].f;
out.push_back(pref[j].s);
}
for(int j=0;j<k-i;j++){
check2+=suff[j].f;
out.push_back(suff[j].s);
}
if(check2>=A and check2 <= 2 *A){
answer(out);
return;
}
}
impossible();
}
