#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);
int e=0;
if(val>=a) id--, e=1;
if(id<=20){
// cerr << "! BT\n";
// 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;
}
}
impossible();
}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);
if(i==k) continue;
sum+=val_p[i-1]; ans.push_back(i);
}
// cerr << "orz\n";
sum+=val; ans.push_back(id+e);
for(int i=id-k+1;i<=id;i++){
val_g.push_back(skim(i));
qm_g.push_back(i);
}
if(sum<=2*a&&sum>=a) answer(ans);
else{
// cerr << "orz\n";
sum-=val; sum+=val_p.back();
ans[sz(ans)-1]=qm_p.back();
// cerr << "! " << sum << '\n';
if(sum>2*a){
impossible();
return;
}
if(sum>=a){
answer(ans);
return;
}
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();
}
}
}
