#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) {
l = -1, r = n;
while (l + 1 < r) {
int m = (l + r) / 2;
sm = 0;
if (m + k > n) {
r = m;
continue;
}
if (!vec[m]) vec[m] = skim(m + 1);
if (1ll * vec[m] * k > 2ll * a) {
r = m;
continue;
}
if (!vec[m + k - 1]) vec[m + k - 1] = skim(m + k);
if (1ll * vec[m + k - 1] * k < a) {
l = 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);
}
