#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
/**
if (skim(2) == 42) {
impossible();
} else {
answer({1, 3});
}**/
std::vector<std::pair<int, int>> intervals;
for(int i = 1; i + k - 1 <= n; i++) {
intervals.push_back({i, i + k - 1});
}
std::map<int, long long> was, asked;
std::function<long long(int)> ask = [&](int i) {
if(was[i]) {
return asked[i];
}
was[i] = 1;
long long t = skim(i);
asked[i] = t;
return t;
};
std::vector<std::pair<long long, int>> v;
std::vector<int> q(n + 1);
for(int i = 1; i <= k; i++) {
v.push_back({ask(i), i});
q[i] = 1;
}
int l = k, r = n, ans = n;
while(l <= r) {
int mid = (l + r) / 2;
if(ask(mid) >= a) {
r = mid - 1;
ans = mid;
}
else {
l = mid + 1;
}
}
for(int i = ans; i >= std::max(k + 1, ans - k - 1); i--) {
v.push_back({ask(i), i});
}
ans = - 1;
for(int mask = 0; mask < (1LL << (v.size())); mask++) {
if(__builtin_popcount(mask) != k) {
continue;
}
long long sum = 0;
for(int i = 0; i < v.size(); i++) {
if(mask & (1LL << i)) {
sum += v[i].first;
}
}
if(sum >= a && sum <= 2LL * a) {
ans = mask;
break;
}
}
if(ans == - 1) {
impossible();
}
else {
std::vector<int> w;
for(int i = 0; i < v.size(); i++) {
if(ans & (1LL << i)) {
w.push_back(v[i].second);
}
}
answer(w);
}
}
