#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include "books.h"
//
// --- 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.
//
typedef long long ll;
std::map<int, ll> asked;
ll get(int p) {
if (asked.count(p)) {
return asked[p];
} else {
return asked[p] = skim(p + 1);
}
}
void solve(int N, int K, long long A, int S) {
std::vector<int> indices;
std::vector<ll> vals;
for (int i = 0; i < K; i++) {
indices.push_back(i);
vals.push_back(get(i));
}
int l = 0, r = N - 1, sol = N - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (get(mid) >= A) {
r = mid - 1;
sol = mid;
} else {
l = mid + 1;
}
}
for (int i = sol; i >= 0 && i >= sol - K; i--) {
indices.push_back(i);
vals.push_back(skim(i));
}
std::sort(indices.begin(), indices.end());
std::sort(vals.begin(), vals.end());
indices.erase(std::unique(indices.begin(), indices.end()), indices.end());
vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
int sz = (int) vals.size();
for (int mask = 0; mask < (1 << sz); mask++) {
if (__builtin_popcount(mask) != K) {
continue;
}
ll sum = 0;
for (int i = 0; i < sz; i++) {
if ((mask >> i) & 1) {
sum += vals[i];
}
}
if (A <= sum && sum <= 2 * A) {
std::vector<int> ret;
for (int i = 0; i < sz; i++) {
if ((mask >> i) & 1) {
ret.push_back(indices[i] + 1);
}
}
answer(ret);
return;
}
}
impossible();
}
