#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int M = 1e5 + 10;
long long a[M];
void solve(int N, int K, long long A, int S) {
/*
// TODO implement this function
if (skim(2) == 42) {
impossible();
} else {
answer({1, 3});
}
*/
set<pair<long long, int>> dig;
// first K elements
long long s = 0;
for(int i = 1; i <= K; i++) {
a[i] = skim(i);
s += a[i];
dig.insert({a[i], i});
}
if(s > 2 * A) {
impossible();
}
if(s >= A && s <= 2 * A) {
vector<int> answ;
for(int i = 1; i <= K; i++) {
answ.push_back(i);
}
answer(answ);
}
int ina = K, inb = N, answ = -1;
while(ina <= inb) {
int mid = (ina + inb) / 2;
a[mid] = skim(mid);
if(a[mid] >= A) {
answ = mid;
inb = mid - 1;
} else {
ina = mid + 1;
}
}
if(answ != -1) {
long long curr = s - a[K] + a[answ];
if(curr >= A && curr <= 2 * A) {
vector<int> v;
for(int i = 1; i < K; i++) {
v.push_back(i);
} v.push_back(answ);
answer(v);
}
answ--;
} else {
answ = N;
}
int cnt = 0;
while(cnt < K && answ > 0) {
dig.insert({skim(answ), answ});
cnt++, answ--;
}
vector<pair<long long, int>> digi;
for(auto u: dig) {
digi.push_back(u);
}
/*
if(si < A) {
impossible();
}
*/
assert(dig.size() <= 20);
int n = digi.size();
for(int mask = 0; mask < (1 << n); mask++) {
int ct = __builtin_popcount(mask);
if(ct != K) continue;
long long sx = 0;
vector<int> vi;
for(int i = 0; i < n; i++) {
if(mask & (1 << i)) {
sx += digi[i].first;
sx = min(sx, 2 * A + 2);
vi.push_back(digi[i].second);
}
}
if(sx >= A && sx <= 2 * A) {
answer(vi);
}
}
impossible();
}
