#include <bits/stdc++.h>
#include "books.h"
#define ll long long
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.
//
void solve(int N, int K, long long A, int S) {
// TODO implement this function
vector <ll> a(N+1,0);
ll s1=0,s2=0;
for(int i=1; i<=K; i++) a[i]=skim(i),s1+=a[i];
for(int i=N; i>=N-K+1; i--) a[i]=skim(i),s2+=a[i];
if(s1>2*A || s2<A){
impossible();
return;
}
if(s1>=A){
vector <int> cur;
for(int i=1; i<=K; i++) cur.push_back(i);
answer(cur);
return;
}
if(s2<=2*A){
vector <int> cur;
for(int i=N-K+1; i<=N; i++) cur.push_back(i);
answer(cur);
return;
}
ll s=s1,l=-1,r=-1;
for(int i=K; i; i--){
s-=a[i];
s+=a[N-i+K];
if(s>=A and s<=A+A){
vector <int> cur;
for(int j=1; j<i; j++) cur.push_back(j);
for(int j=N-i+K; j<=N; j++) cur.push_back(j);
answer(cur);
return;
}
if(s>A+A){
l=i-1;
r=N-i+K;
break;
}
}
s-=a[r];
int L=K+1,R=N-K;
while(L<=R){
int mid=(L+R)>>1;
int ss=skim(mid);
if(s+ss>=A and s+ss<=A+A){
vector <int> cur;
for(int i=1; i<=l; i++) cur.push_back(i);
for(int i=r; i<=N; i++) cur.push_back(i);
cur.push_back(mid);
answer(cur);
}else if(s+ss>A+A){
R=mid-1;
}else L=mid+1;
}
assert(0);
}
