#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});
}
int l = 0, r = intervals.size() - 1, ans = - 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;
};
while(l <= r) {
int mid = (l + r) / 2;
long long sum = 0;
for(int i = intervals[mid].first; i <= intervals[mid].second; i++) {
sum += ask(i);
}
if(sum > 2 * a) {
r = mid - 1;
}
else if(sum < a) {
l = mid + 1;
}
else {
ans = mid;
break;
}
}
if(ans == - 1) {
impossible();
}
else {
std::vector<int> w;
for(int i = intervals[ans].first; i <= intervals[ans].second; i++) {
w.push_back(i);
}
answer(w);
}
}
