#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.
//
vector<long long> val(100005, -1);
long long qry(int x){
if(val[x]!=-1)return val[x];
return val[x]=skim(x);
}
void solve(int N, int k, long long A, int S) {
int hi=N,lo=1,m;
int ans=N+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;
long long c=qry(m);
if(c>=A){
ans=m;
hi=m-1;
}
else{
lo=m+1;
}
}
if(ans<k){
impossible();
return;
}
if(ans!=N+1){ // if >= A exists
vector<int> out;
long long sm=0;
for(int i=1;i<=k-1;i++){ //k-1 prefix
sm+=qry(i);
out.push_back(i);
}
out.push_back(ans); // first occurence >= A
sm+=qry(ans);
if(sm>=A and sm <= 2*A){
answer(out);
return;
}
else if (ans==k){ // then there wouldnt be another config that worsk
impossible();
return;
}
}
for(int i=0;i<=k;i++){ // prefix size
long long check2=0;
vector<int> out;
for(int j=1;j<=i;j++){
check2+=qry(j); // prefix
out.push_back(j);
}
for(int j=ans-1;j>=ans-(k-i);j--){
check2+=qry(j); // suffix
out.push_back(j);
}
if(check2>=A and check2 <= 2*A){
answer(out);
return;
}
}
impossible();
}
