#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.
//
vector<long long> cache;
long long qry(int n) {
if (cache[n] != -1) return cache[n];
return cache[n] = skim(n + 1);
}
void solve(signed N, signed K, long long A, signed S) {
cache.resize(N, -1);
int low = 0, high = N - 1, ans = N;
if (S >= 170) {
ans = -1;
while (low <= high) { // 17 queries
int x = (low + high) / 2;
if (qry(x) >= A) ans = x, high = x - 1;
else low = x + 1;
}
if (ans != -1 && qry(ans) <= 2 * A) {
long long crnts = qry(ans);
for (int i = 0; i < K - 1; i++) crnts += qry(i);
if (crnts <= 2 * A) {
vector<int> res = { ans + 1 };
for (int i = 0; i < K - 1; i++) res.push_back(i + 1);
answer(res);
return;
}
}
if (ans == -1) ans = N;
if (K > ans) {
impossible();
return;
}
}
for (int i = 0; i < K; i++) qry(i); // 20 queries
for (int i = ans - K; i < ans; i++) qry(i);
vector<long long> funny;
for (int i = K; i >= 0; i--) {
long long crnts = 0;
for (int j = 0; j < i; j++) crnts += qry(j);
for (int j = ans - (K - i); j < ans; j++) crnts += qry(j);
funny.push_back(crnts);
}
if (funny[0] > 2 * A || funny.back() < A) {
impossible();
return;
}
if (funny[0] >= A) {
vector<int> res;
for (int i = 0; i < K; i++) res.push_back(i + 1);
answer(res);
return;
}
int idx = lower_bound(funny.begin(), funny.end(), A) - funny.begin();
low = K - idx, high = ans - idx;
int _ans = -1, asd = 2 * A + 1;
while (low <= high) { // 17 queries
int x = (low + high) / 2;
if (funny[idx - 1] - qry(K - idx) + qry(x) >= A) _ans = x, high = x - 1, asd = funny[idx - 1] - qry(K - idx) + qry(x);
else low = x + 1;
}
if (asd > 2 * A) {
low = K - 2, high = _ans - 2, ans = -1;
int csum = qry(_ans - 1);
for (int i = 0; i < K - 2; i++) csum += qry(i);
while (low <= high) {
int x = (low + high) / 2;
if (csum + qry(x) >= A) ans = x, high = x - 1;
else low = x + 1;
if (csum + qry(x) >= A && csum + qry(x) <= 2 * A) break;
}
if (csum + qry(ans) > 2 * A) {
impossible();
return;
}
vector<int> res = { _ans, ans + 1 };
for (int i = 0; i < K - 2; i++) res.push_back(i + 1);
answer(res);
return;
}
vector<int> res = { _ans + 1 };
for (int i = 0; i < K - idx; i++) res.push_back(i + 1);
for (int i = ans - idx + 1; i < ans; i++) res.push_back(i + 1);
answer(res);
}
