#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
void solve(int N, int K, ll A, int S) {
int lo = 1, hi = N;
// binary search pierwszego skim(i) >= A
if (skim(N) < A) {
impossible();
return;
}
while (lo < hi) {
int mid = (lo + hi) / 2;
if (skim(mid) >= A) hi = mid;
else lo = mid + 1;
}
if (lo <= K - 1) {
impossible();
return;
}
vector<ll> val;
vector<int> ind;
// 1 .. min(K, lo)
for (int i = 1; i <= min(K, lo); ++i) {
val.push_back(skim(i));
ind.push_back(i);
}
// max(K+1, lo-K+1) .. lo
for (int i = max(K + 1, lo - K + 1); i <= lo; ++i) {
val.push_back(skim(i));
ind.push_back(i);
}
// przypadek: bierzemy lo + K-1 najmniejszych
ll suma = skim(lo);
for (int i = 0; i < K - 1; ++i) suma += val[i];
if (A <= suma && suma <= 2 * A) {
vector<int> ans;
for (int i = 0; i < K - 1; ++i) ans.push_back(ind[i]);
ans.push_back(lo);
answer(ans);
return;
}
// sliding window po uporządkowanych indeksach
suma = 0;
for (int i = 0; i < K; ++i) suma += val[i];
for (int i = K; i < (int)val.size(); ++i) {
if (A <= suma && suma <= 2 * A) {
vector<int> ans;
for (int j = i - K; j < i; ++j)
ans.push_back(ind[j]);
answer(ans);
return;
}
suma += val[i];
suma -= val[i - K];
}
// ostatnie okno
if (A <= suma && suma <= 2 * A) {
vector<int> ans;
for (int i = val.size() - K; i < (int)val.size(); ++i)
ans.push_back(ind[i]);
answer(ans);
return;
}
impossible();
}
