#include "books.h"
#include <bits/stdc++.h>
using namespace std;
int64_t cached[100005];
set<int> _s;
long long get(int x) {
_s.insert(x);
return cached[x] ? cached[x] : cached[x] = skim(x);
}
void solve(int N, int K, long long A, int S) {
int64_t SUM = 0;
for (int i = 1; i <= K; i++) SUM += get(i);
if (1) {
int64_t O = SUM - get(K);
int lo = K-1, hi = N+1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (!_s.empty()) {
auto it = _s.upper_bound(lo);
if (it != _s.end() && *it < hi) mid = *it;
}
int64_t T = get(mid) + O;
if (A <= T && T <= 2*A) {
vector<int> ans;
for (int i = 1; i < K; i++) ans.emplace_back(i);
ans.emplace_back(mid);
answer(ans);
return;
}
if (get(mid) >= A) hi = mid;
else lo = mid;
}
N = hi-1;
}
if (N < K) {
impossible();
return;
}
if (A <= SUM && SUM <= 2*A) {
vector<int> ans;
for (int i = 1; i <= K; i++) ans.emplace_back(i);
answer(ans);
return;
}
if (SUM > 2 * A) {
impossible();
return;
}
for (int i = K; i >= 1; i--) {
SUM -= get(i);
SUM += get(N-(K-i+1)+1);
if (SUM >= A) {
SUM -= get(N-(K-i+1)+1);
int lo = i, hi = N-(K-i+1)+2;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (!_s.empty()) {
auto it = _s.upper_bound(lo);
if (it != _s.end() && *it < hi) mid = *it;
}
int64_t T = SUM + get(mid);
if (A <= T && T <= 2*A) {
vector<int> ans;
for (int p = 1; p < i; p++) ans.emplace_back(p);
ans.emplace_back(mid);
for (int p = N-(K-i)+1; p <= N; p++) ans.emplace_back(p);
answer(ans);
return;
}
if (T >= A) hi = mid;
else lo = mid;
}
assert(false);
}
}
impossible();
}
