#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});
}
*/
vector<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.push_back({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 + 1, 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;
long long si = 0;
while(cnt < K) {
if(a[answ]) break;
a[answ] = skim(answ);
si += a[answ];
dig.push_back({a[answ], answ});
cnt++, answ--;
}
if(si < A) {
impossible();
}
assert(dig.size() <= 20);
int n = dig.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 += dig[i].first;
vi.push_back(dig[i].second);
}
}
if(sx >= A && sx <= 2 * A) {
answer(vi);
}
}
impossible();
}
