#include <bits/stdc++.h>
#include "books.h"
using namespace std;
void solve(int N, int K, long long A, int S) {
// TODO implement this function
//k books, sum of A
typedef long long ll;
//x, x+1, x+2, x+3, x+4, x+5... and so on
int extrasum = 0;
for (int x = 0; x < K; x++){
extrasum += x;
}
//we want A <= x*K + extrasum <= 2*A
//x*K + extrasum >= A
//x*K >= A-extrasum
//x >= (A-extrasum)/K
ll target = (A - extrasum)/K + ((A - extrasum)%K != 0);
//to do: check rounding
if (A - extrasum <= 0) {impossible(); return;}
int l = 1, r = N+1-K, ans = N+1-K;
while (l <= r){
int m = (l+r)/2;
ll res = skim(m);
if (res >= target){
r = m-1;
ans = m;
}
else{
l = m+1;
}
}
ll sum = 0; deque<ll> vals;
for (int x = ans; x < ans + K; x++){
ll res = skim(x);
sum += res; vals.push_back(res);
}
if (sum < A){
impossible();
}
int lowest = ans;
for (int x = 0; x < min(10, lowest-1); x++){
if (sum <= 2LL*A){
vector<int> res; for (int x = lowest; x < lowest+K; x++) res.push_back(x);
answer(res);
}
else{
sum -= vals.back();
vals.pop_back();
lowest--;
long long v = skim(lowest);
vals.push_front(v);
sum += v;
}
}
if (sum <= 2LL*A){
vector<int> res; for (int x = lowest; x < lowest+K; x++) res.push_back(x);
answer(res);
}
impossible();
}
