#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(K==3&&N==S&&N<=1000){
long long arr[N];
for(int i = 0;i<N;i++){
arr[i] = skim(i+1);
}
for(int i = 0;i<N;i++){
for(int j = i+1;j<N;j++){
int it = lower_bound(arr+j+1,arr+N,A-arr[i]-arr[j])-arr;
if(it==N)continue;
if(arr[i]+arr[j]+arr[it]<=2*A){
answer({i+1,j+1,it+1});
}
}
}
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 ;
}
}
}
}
