#include <bits/stdc++.h>
using namespace std;
#include "books.h"
long long val[100001];
int xd= 0;
int s;
long long qu(int i){
if(val[i]!=-1)return val[i];
xd++;
if(xd>s)assert(0);
return val[i] = skim(i);
}
void solve(int N,int K,long long A,int S){
if(N<=S){
long long arr[N],pref[N];
for(int i = 0;i<N;i++){
arr[i] = skim(i+1);
pref[i] = arr[i];
if(i)pref[i]+=pref[i-1];
}
for(int i = 0;i<N;i++){
long long sum = 0;
for(int j = i;j<min(N,i+K);j++){
sum+=arr[j];
if(sum>2*A)break;
if(j==i+K-1){
if(sum>=A){
vector<int> v;
for(int e = i;e<=j;e++){
v.push_back(e);
}
answer(v);
}
break;
}
int l = j+1 , r = N;
while(l<=r){
int mid = (l+r)/2;
int rem = K-(j-i+1);
long long val = pref[mid+rem-1]-(mid==0?0:pref[mid-1]);
if(sum+val<A)l = mid+1;
else if(sum+val>2*A)r = mid-1;
else {
vector<int> v;
for(int e = i;e<=j;e++){
v.push_back(e);
}
for(int e = mid;e<mid+rem;e++)v.push_back(e);
answer(v);
}
}
}
}
impossible();
}else{
memset(val,-1,sizeof val);
s = S;
long long l = 1 , r = N-K+1 , ans = N-K+2 , sum = 0;
while(l<=r){
int mid = (l+r)/2;
long long val = 0;
for(int i = mid;i<mid+K;i++){
val+=qu(i);
}
if(val>=A){
r = mid-1;
sum = val;
ans = mid;
}else l = mid+1;
}
if(ans==N-K+2){
for(int i = N-K+2;i<=N;i++)sum+=qu(i);
}else sum-=qu(ans+K-1);
vector<int> xd;
for(int i = 1;i<=N;i++)if(i<ans||i>=ans+K-1)xd.push_back(i);
l = 0 , r = xd.size()-1;
while(l<=r){
int mid = (l+r)/2;
if(sum+qu(xd[mid])<A){
l= mid+1;
}else if(sum+qu(xd[mid])>2*A){
r = mid-1;
}else{
vector<int> v;
for(int i = ans;i<ans+K-1;i++)v.push_back(i);
v.push_back(xd[mid]);
answer(v);
return ;
}
}
if(ans==1)impossible();
ans--;sum = 0;
for(int i = ans;i<ans+K-1;i++)sum+=qu(i);
l = 0 , r = xd.size()-1;
while(l<=r){
int mid = (l+r)/2;
if(sum+qu(xd[mid])<A){
l= mid+1;
}else if(sum+qu(xd[mid])>2*A){
r = mid-1;
}else{
vector<int> v;
for(int i = ans;i<ans+K-1;i++)v.push_back(i);
v.push_back(xd[mid]);
answer(v);
return ;
}
}
if(ans==1)impossible();
ans--;sum = 0;
for(int i = ans;i<ans+K-1;i++)sum+=qu(i);
l = 0 , r = xd.size()-1;
while(l<=r){
int mid = (l+r)/2;
if(sum+qu(xd[mid])<A){
l= mid+1;
}else if(sum+qu(xd[mid])>2*A){
r = mid-1;
}else{
vector<int> v;
for(int i = ans;i<ans+K-1;i++)v.push_back(i);
v.push_back(xd[mid]);
answer(v);
return ;
}
}
if(ans==1)impossible();
ans--;sum = 0;
for(int i = ans;i<ans+K-1;i++)sum+=qu(i);
l = 0 , r = xd.size()-1;
while(l<=r){
int mid = (l+r)/2;
if(sum+qu(xd[mid])<A){
l= mid+1;
}else if(sum+qu(xd[mid])>2*A){
r = mid-1;
}else{
vector<int> v;
for(int i = ans;i<ans+K-1;i++)v.push_back(i);
v.push_back(xd[mid]);
answer(v);
return ;
}
}
}
}
