#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#define ll long long
void solve(int n, int k, ll A, int S) {
vector<ll> v(n+1, 0);
vector<int> ans;
int l=0, r=n, m;
ll pre=0, sum=0;
for(int i=1; i<k; i++){
v[i] = skim(i);
pre += v[i];
if(pre > 2*A){
impossible();
return;
}
}
//lower bound binary search
while(r-l > 1){
m = (l+r)/2;
if(!v[m]) v[m] = skim(m);
if(v[m]*k < A){
l = m;
}
else{
r = m;
}
}
l = r;
for(int i=l-1; i>= max(1, l-k+1); i--){
if(!v[i]) skim(i);
}
for(int i=l+1; i<=min(n, l+k-1); i++){
if(!v[i]) skim(i);
}
for(int i=max(0, l-k); i<l; i++){
sum += v[i];
if(sum > 2*A) break;
}
for(int i=max(1, l-k+1); i<=min(l, n-k+1); i++){
sum += v[i+k-1]-v[i-1];
if(sum > 2*A) break;
if(sum >= A){
for(int j=i; j<i+k; j++){
ans.push_back(j);
}
answer(ans);
return;
}
}
for(int i=max(k, l-k+1); i<=min(n, l+k-1); i++){
if(v[i] + pre >= A && v[i] + pre <= 2*A){
for(int j=1; j<k; j++){
ans.push_back(j);
}
ans.push_back(i);
answer(ans);
return;
}
}
impossible();
}
