#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
//
// --- 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;
vec[0] = skim(1);
sm += vec[0];
if (vec[0] * k > 2 * a) {
impossible();
return;
}
vec[n - 1] = skim(n);
if (vec[n - 1] * k < a) {
impossible();
return;
}
for (int i = 1; i < k - 1; ++i) {
vec[i] = skim(i + 1), sm += vec[i];
if (vec[0] * k > 2 * a) break;
}
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) {
for (int i = 0; i <= r; ++i) {
if (!vec[i]) vec[i] = skim(i + 1);
}
sm = 0;
for (int i = 0; i < k; ++i) sm += vec[i];
if (sm >= a && sm <= 2 * a) {
vector<int> ans;
for (int i = 1; i <= k; ++i) ans.push_back(i);
answer(ans);
return;
}
for (int i = 1; i + k - 1 <= r; ++i) {
sm -= vec[i - 1];
sm += vec[i + k - 1];
if (sm >= a && sm <= 2 * a) {
vector<int> ans;
for (int j = i + 1; j <= i + k; ++j) ans.push_back(j);
answer(ans);
return;
}
}
impossible();
}
vector<int> ans;
for (int i = 1; i <= k - 1; ++i) ans.push_back(i);
ans.push_back(r + 1);
answer(ans);
}
