#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;
}
}
vector<pair<int, ll>> items;
for (int x = max(1, ans-10); x < min(N+1, ans+K+10); x++){
items.push_back({x, skim(x)});
}
for (int bm = 0; bm < (1<<items.size()); bm++){
if (__builtin_popcount(bm) != K) continue;
ll sum = 0;
for (int x = 0; x < (int)items.size(); x++){
if (bm & (1<<x)){
sum += items[x].second;
}
}
if (A <= sum && sum <= 2LL*A){
vector<int> indices;
for (int x = 0; x < (int)items.size(); x++){
if (bm & (1<<x)){
indices.push_back(items[x].first);
}
}
answer(indices);
return;
}
}
impossible();
}
