#include "books.h"
#include <bitset>
using namespace std;
vector<long long> res;
pair<long long,long long> sskim(int l) {
if(res[l] ==-1) {
long long t = skim(l+1);
res[l]=t;
return {t,t};
}else {
return {res[l],res[l]};
}
}
void solve(int N, int K, long long A, int S) {
long long l = 0;
res = vector<long long>(N,-1);
vector<pair<int,long long>> rel;
for (int i = 0; i < K-1; ++i) {
int t = sskim(i).second;
l+=t;
rel.push_back({l,t});
}
int min = 0;
int max = N;
while(max-min>1) {
int mid = (min+max)/2;
if(sskim(mid).second>2*A-l) {
max = mid;
}else {
min = mid;
}
}
for (int i = min; i >= std::max(min-K,K); --i) {
auto [a,b] = sskim(i);
rel.push_back({i,sskim(i).second});
}
int v = rel.size();
for (int i = 0; i < 1<<v; ++i) {
bitset<20> b = i;
long long r = 0;
if(b.count()!=K) continue;
for (int j = 0; j < v; ++j) {
if(b[j]) r+=rel[j].second;
}
if(r<=2*A && A<=r) {
vector<int> re;
for (int j = 0; j < v; ++j) {
if(b[j]) re.push_back(rel[j].first+1);
}
answer(re);
exit(0);
}
}
impossible();
}
