#include <bits/stdc++.h>
#include "books.h"
#define ll long long
#define sz(v) (int)(v.size())
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, ll a, int s){
auto bb=[&](){
int l=1, r=n;
while(l<r){
int mid=(l+r)/2;
ll at=skim(mid);
if(at<a) l=mid+1;
else r=mid;
}
return l;
};
int id=bb();
ll val=skim(id);
id--;
if(id<=20){
// backtracking, para nao ter problema com repeticao
vector<ll>v; v.push_back(val);
vector<int>qm; qm.push_back(id+1);
for(int i=1;i<=id;i++) v.push_back(skim(i)), qm.push_back(i);
for(int mask=0;mask<(1<<(sz(v)));mask++){
ll sum=0;
int qtd=0;
for(int i=0;i<sz(v);i++) if(mask&(1<<i)) qtd++, sum+=v[i];
if(qtd==k&&a<=sum&&sum<=2*a){
vector<int>ans;
for(int i=0;i<sz(v);i++) if(mask&(1<<i)) ans.push_back(qm[i]);
answer(ans);
return;
}
}
}else{
// fzr namoral
vector<ll> val_p, val_g;
vector<int> qm_p, qm_g;
vector<int>ans;
ll sum=0;
for(int i=1;i<k;i++){
val_p.push_back(skim(i));
qm_p.push_back(i);
sum+=val_p[i-1]; ans.push_back(i);
}
sum+=val; ans.push_back(id+1);
for(int i=id-k+1;i<=id;i++){
val_g.push_back(skim(i));
qm_g.push_back(i);
}
if(sum<=2*a) answer(ans);
else{
sum-=val; sum+=val_g.back();
ans[sz(ans)-1]=qm_g.back();
for(int i=0;i<sz(val_p);i++){
sum-=val_p[i]; sum+=val_g[i];
ans[i]=qm_g[i];
if(sum>=a){
answer(ans);
return;
}
}
impossible();
}
}
}
