#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
vector<long long> vec(n);
long long sm = 0;
for (int i = 0; i < k - 1; ++i) vec[i] = skim(i + 1), sm += vec[i];
int l = k - 2, r = n - 1;
while (l + 1 < r) {
int m = (l + r) / 2;
long long b = vec[m];
if (!b) b = skim(m + 1);
vec[m] = b;
if (sm + b >= a) r = m;
else l = m;
}
if (sm + vec[r] > 2 * a || sm + vec[r] < a) {
l = -1, r = n;
while (l + 1 < r) {
int m = (l + r) / 2;
sm = 0;
if (m + k > n) {
r = m;
continue;
}
for (int i = m; i < m + k; ++i) {
if (!vec[i]) vec[i] = skim(i + 1);
sm += vec[i];
}
if (sm >= a) r = m;
else l = m;
}
sm = 0;
if (r + k > n) {
impossible();
return;
}
for (int i = r; i < r + k; ++i) sm += vec[i];
if(sm < a || sm > 2 * a) impossible();
else {
vector<int> ans;
for (int i = r + 1; i <= r + k; ++i) ans.push_back(i);
answer(ans);
}
return;
}
vector<int> ans;
for (int i = 1; i <= k - 1; ++i) ans.push_back(i);
ans.push_back(r + 1);
answer(ans);
}
