#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.
//
using i64 = long long;
void solve(int n, int k, long long A, int S) {
vector <i64> a(n + 1, -1);
auto qry = [&](int x){
return a[x] != -1 ? a[x] : a[x] = skim(x);
};
int l = 0, r = n + 1;
while ( l + 1 < r ){
int m = (l + r) / 2;
if ( qry(m) <= A ) l = m;
else r = m;
}
i64 mn = 0;
for ( int i = 1; i <= k; i++ ) mn += qry(i);
if ( l >= k ){
i64 mx = 0;
for ( int i = l; i > l - k; i-- ) mx += qry(i);
if ( mn <= A * 2 && mx >= A ){
vector <int> p;
for ( int i = 1; i <= l; i++ ){
if ( i <= k || i > l - k ) p.push_back(i);
}
int m = p.size();
for ( int mask = 0; mask < (1 << m); mask++ ){
if ( __builtin_popcount(mask) != k ) continue;
i64 sum = 0;
vector <int> idx;
for ( int i = 0; i < m; i++ ){
if ( mask >> i & 1 ){
idx.push_back(p[i]);
sum += qry(p[i]);
}
}
if ( sum >= A && sum <= A * 2 ) answer(idx);
}
}
}
if ( r <= n ){
i64 v = mn - qry(k) + qry(r);
if ( v <= A * 2 ){
vector <int> idx;
for ( int i = 1; i < k; i++ ) idx.push_back(i);
idx.push_back(r);
answer(idx);
}
}
impossible();
}
