#include <bits/stdc++.h>
#include "books.h"
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
long long sum = 0;
vector<pair<int,long long>> z;
for (int i = 1; i < K; i++) {
z.push_back(make_pair(i,skim(i)));
sum += z.back().second;
}
if (sum > 2*A) impossible();
int ll = K, rr = N;
while (ll < rr) {
int mid = (ll+rr+1) / 2;
if (skim(mid)+sum <= 2*A) ll = mid;
else rr=mid-1;
}
long long tmp = skim(ll);
if (tmp+sum > 2*A) impossible();
z.push_back(make_pair(ll,tmp));
for (int i = max(K,ll-K+1); i < ll; i++) {
z.push_back(make_pair(i,skim(i)));
}
int n2 = z.size();
for (int i = (1<<n2)-1; i >= 0; i--) {
if (__builtin_popcount(i) != K) continue;
long long sum = 0;
vector<int> v;
for (int j = 0; j < n2; j++) {
if ((i>>j)&1) {
sum += z[j].second;
if (sum > A * 2) break;
v.push_back(z[j].first);
}
}
if (sum >= A and sum <= A * 2) {
answer(v);
}
}
impossible();
}
