#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.
//
typedef long long ll;
const int MAX_N=1e5+10;
vector<ll> book;
ll libro(int id){
if(book[id]!=-1) return book[id];
return book[id]=skim(id);
}
void solve(int N, int K, long long A, int S) {
book.resize(N+1);
for(int i=0;i<=N;i++) book[i]=-1;
for(int i=1;i<K;i++){
book[i]=libro(i);
}
ll sk=0;
vector<int> ans;
for(int i=1;i<K;i++){
sk+=libro(i);
ans.push_back(i);
}
if(sk>=A){
if(sk+skim(K)>2*A) impossible();
else{
ans.push_back(K);
answer(ans);
}
}
bool ok=0;
int l=0,r=N;
while(r-l>1){
int mid=(l+r)/2;
if(libro(mid)>=A) r=mid;
else l=mid+1;
}
int id=r;
if(libro(l)>=A) id=l;
if(sk+libro(id)>=A && sk+libro(id)<=2LL*A){
ans.push_back(id);
ok=1;
}
else{
if(libro(id)>=A)
id--;
sk+=libro(id);
ans.push_back(id);
id--;
for(int i=0;i<K-1;i++){
int mi=ans[0];
ans.erase(ans.begin());
ans.push_back(id);
sk-=libro(mi); sk+=libro(id);
if(sk>=A){
ok=1;
break;
}
id--;
}
}
if(!ok) impossible();
else answer(ans);
}
